首页 > 代码库 > codeforces 427E

codeforces 427E

2024-07-30 12:17:08   223人阅读

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

思路：

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

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

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

code：

 1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int a[1001010], n, m; 5 ll sl[1001010], sr[1010000]; 6  7 void solve(){ 8     for (int i = 1; i <= n; ++i){ 9           scanf("%d", &a[i]);10           if ((i-1) % m == 0) sl[i] = sl[max(i-m, 0)] + a[i];11     }12     for (int i = n; i >= 1; --i)13          if ((n-i) % m == 0)  sr[i] = sr[min(n+1, i + m)] + a[i];14     ll ans = 1LL<<50;15     int l, r, lr, rr;16     int cnt = (n - 1) / m + 1;17     rr = n - (cnt-1) * m;18 //    cout << rr << endl;19     ans = sr[rr] - (ll)cnt * a[1];20 //    cout << ans << endl;21     lr = 1 + (cnt-1) * m;22     ans = min((ll)cnt * a[n] - sl[lr], ans);23 //    cout << ans << endl; 24     ll tmp, cnt1, cnt2;25     for (int i = 2; i <= n; ++i){26         l = i - 1, r = i;27         cnt1 = (l - 1) / m + 1, cnt2 = (n - r) / m + 1;28         lr = 1 + (cnt1 - 1) * m, rr = n - (cnt2 - 1) * m;29 //        if (i == 2){30 //              printf("lr = %d rr = %d\n", lr, rr);31 //        }32         tmp = (ll)a[r] * cnt1 - sl[lr] + sr[rr] - (ll)a[r] * cnt2;33 //        printf("%d %lld\n", i, tmp);34         ans = min(ans, tmp);35     }36     cout << ans * 2 << endl;37 }38 int main(){39 //    freopen("a.in", "r", stdin);40     while (scanf("%d%d", &n, &m) != EOF){41          solve();42     }    43 }
View Code

 

codeforces 427E


联系
我们