codeforces 427E

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：给定一位空间里n个点的坐标，每个坐标有一个罪犯，现在要建一个警局，并且这个警局只有一辆车，车一次最多载m个人，问应建在哪是的抓回所有罪犯的路程和最小。

思路：

很明显建在罪犯的点上一定可以找到最优解。

那么直接枚举建在哪一个点。。

那么抓罪犯肯定从两边抓最优。所以预处理两个数组即可。。

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[], n, m;
ll sl[], sr[]; void solve(){
for (int i = ; i <= n; ++i){
scanf("%d", &a[i]);
if ((i-) % m == ) sl[i] = sl[max(i-m, )] + a[i];
}
for (int i = n; i >= ; --i)
if ((n-i) % m == ) sr[i] = sr[min(n+, i + m)] + a[i];
ll ans = 1LL<<;
int l, r, lr, rr;
int cnt = (n - ) / m + ;
rr = n - (cnt-) * m;
// cout << rr << endl;
ans = sr[rr] - (ll)cnt * a[];
// cout << ans << endl;
lr = + (cnt-) * m;
ans = min((ll)cnt * a[n] - sl[lr], ans);
// cout << ans << endl;
ll tmp, cnt1, cnt2;
for (int i = ; i <= n; ++i){
l = i - , r = i;
cnt1 = (l - ) / m + , cnt2 = (n - r) / m + ;
lr = + (cnt1 - ) * m, rr = n - (cnt2 - ) * m;
// if (i == 2){
// printf("lr = %d rr = %d\n", lr, rr);
// }
tmp = (ll)a[r] * cnt1 - sl[lr] + sr[rr] - (ll)a[r] * cnt2;
// printf("%d %lld\n", i, tmp);
ans = min(ans, tmp);
}
cout << ans * << endl;
}
int main(){
// freopen("a.in", "r", stdin);
while (scanf("%d%d", &n, &m) != EOF){
solve();
}
}