51Nod 1173. 石子分配(中位数距离) 日付: 10月 17, 2018 リンクを取得 Facebook × Pinterest メール 他のアプリ [石子分配问题 - 51Nod](https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1173) ## Problem $n$堆石子摆成**环**，需要使每堆石子数量均匀，每次操作只能从一堆向隔了$k$的另一堆移动一个石子。问最少需要移动多少次。 数据范围：$2 \le n \le 50000, 0 \le k < n$ ## Solution 首先可以发现距离$k$这个限制很容易去掉，相当于把$n$堆石子分成了若干个环，环间无法交换，环内相邻堆可以交换。最后只需要把这些环的答案加起来就好了。 如果没有环的限制，那么问题就比较简单了，可以从左到右贪心。比如对于"1, 3, 9, 7"，最后要匀成5，可以把每一项减去5，得到"-4 -2 4 2"，然后算前缀和得到"-4 -6 -2 0"，这个序列中负数表示在该位置需要从右边移过来多少个，正数表示在该位置需要向右边移过去多少个，最后求绝对值的和得到12就是答案。 然后考虑环的限制条件，最优的情况下，一定存在只出不进和只进不出的堆，将环切断。那么暴力的做法就很明显了，枚举每一堆作为起点，按照非环处理即可。但是这样是$O(N^2)$的，必然超时。考虑依次更换起点时，前缀和序列的变化，比如"-4 -6 -2 0"，如果以第二位作起点，序列就变为"-2 2 4 0"，如果以第三位作起点，就变为"4 6 2 0"，相当于每次把所有数都减去第一个数，再把第一个数移到最后，每个数的相对距离保持不变。如果把第一次求绝对值的和看作是求所有数到0的距离之和，之后每次都相当于求所有数到一个新的基准的距离之和，观察可以发现这些基准就在前缀和序列本身里面取。问题转化为：对于$x$轴上的点，找出其中一个点，到所有点距离之和最小，并求出这个距离。最优的点就是中位数(如果是偶数个点，那么两个中间点都是最优)。这样时间复杂度就是排序的$O(NlogN)$。 ## Code ```c++ #include <bits/stdc++.h> using namespace std; using LL = long long; int main() { int n, k; scanf("%d%d", &n, &k); LL tot = 0; vector<int> A(n); for (int i = 0; i < n; i++) scanf("%d", &A[i]), tot += A[i]; LL avg = tot / n,ans = 0; vector<char> Vis(n); for (int i = 0; i < n; i++) { if (Vis[i]) continue; vector<LL> B; for (int j = i; !Vis[j]; j = (j + k + 1) % n) Vis[j] = 1, B.push_back(A[j] - avg); partial_sum(B.begin(), B.end(), B.begin()); int m = int(B.size()); sort(B.begin(), B.end()); LL bias = B[m / 2]; LL tmp = 0; for (auto& x : B) tmp += abs(x - bias); ans += tmp; } printf("%lld\n", ans); } ``` コメント
コメント
コメントを投稿