环形纸牌问题
(公式推导 + 转化为货仓选址问题)
每个人最后获得的均等纸牌数为纸牌总数 Sum/N ,记为 avg 。
假设 num[i] 表示第 i 个人给第 i − 1个人的纸牌数;若num[i] 为负数,则表示第i−1个人给第i个人传的纸牌数。
特别地, num[1] 表示第1个人给第N个人的纸牌数。
那么,最终的答案就等于min(∣num[1]∣+∣num[2]∣+⋯+∣num[N]∣) 。
第 i 个人最后的纸 = 他原有纸牌 + 别人给他的 − 他给别人的 = 均等纸牌数。
a[i]+num[i+1]−num[i]=avg
变换得:
num[N]=num[1]−[a[1]+a[2]+⋯+a[N−1]−(N−1)×avg]
令:num[1] 后面的东西为 C[i]
C[i]=C[i−1]+a[i]−avg
那么,最后的答案就转变成了min(∣num[1]−C[1]∣+∣num[1]−C[2]∣+⋯+∣num[1]−C[N−1]∣)
就是货仓选址问题,排序,点num[1]取中位数,即为结果
时间复杂度 $O(nlogn)$
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 20;
LL c[N];
int a[N];
int n;
int main()
{
cin >> n;
LL sum = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
sum += a[i];
}
LL avg = sum / n;
for (int i = 1; i < n; i++) {
c[i] = c[i - 1] + a[i] - avg;
}
//转化为货仓选址问题
sort(c, c + n);
LL res = 0;
for (int i = 0; i < n; i++) {
res += abs(c[i] - c[n/2]);
}
cout << res << endl;
return 0;
}