今天写题，突然发现环形分割纸牌突然不会了，真是羞愧，写篇博客警示自己
连这种基础问题都做不出来，怎么应对其变形呢
首先简单一些，断成链，此时对于链两端的人，他们只可能从右边或者左边的人获取纸牌
而对于链中间的人，他们有两种获取途径。
那么从左边的人（1号）看起，如果要让他获取足够的卡牌数目，那么他只可能从右边的人获取。
当他拿够足够的卡牌，现在要给他右边的人（2号）足够的卡牌，此时肯定不能从1号手中拿（那你刚才还给1号卡牌干什么），所以只能从右边的人手中拿，以此类推，那么每个人都只能从他右边的人手中拿到卡牌。此时，便可以一遍推过去得到答案。
问题是，怎么给呢，如果某个人的卡牌不够给怎么办？
其实考虑一下，并不影响最终答案，因为他缺的卡牌数，最终一定是要从他右边的人拿的，而如果他多出来了卡牌，那他是一定要给他右边的人的，而总卡牌数是一定的，遍历到最后一个人的时候，他此时的卡牌数一定正好是平均数。
代码如下：若干年前的洛谷代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,k[11000]; 4 int main() 5 { 6 int ans=0,sum=0; 7 scanf("%d",&n); 8 for(int i=1;i<=n;i++) scanf("%d",k+i),sum+=k[i]; 9 sum/=n; 10 for(int i=1;i<=n;i++) 11 { 12 if(k[i]!=sum) k[i+1]+=k[i]-sum,ans++; 13 } 14 printf("%d\n",ans); 15 return 0; 16 }
那么，当这个问题拓展到环形呢，通用的处理方法肯定是将环断开变成链，同时将第1位到第n位复制到第n+1到2*n的位置上
枚举每个起点 i ， 1 ≤ i ≤ n ， 长度为 n 的一段数组，找到最小的那个答案
但是还不够，当n足够大时，枚举起点会导致超时，那么还有什么方法可以优化呢
对于这种求和问题，很容易想到前缀和，如何前缀和
考虑成链时候，答案如何得到
设 数组 k[i] = a[i] - ave，a[i] 为 第 i 个人持有的纸牌数目，则对数组 k 求前缀和后，答案为 ∑| k[i] | ，不要问为什么
那么变成链后呢，如果此时枚举的起点是 beg ， 那么从beg+1 到 n 中的任意一个人 j ，此时的 k[j] = k[j] - k[beg]，而对 n+1 到 beg + n - 1的人 j，则 k[j] = k[n] - k[beg] + k[j-n]
而且易知，k[n] = 0, 那么最终答案就是 ∑| k[i] - k[beg] | 1 ≤ i ≤ n, 1 ≤ beg ≤ n
喝，这不是仓库选址吗，答案最小的时候，一定是 k 数组从大到小后，所有的数相对于中位数的距离之和啊
代码如下
1 #include<bits/stdc++.h> 2 3 typedef long long LL; 4 const int MAXN = 1e6 + 10; 5 using namespace std; 6 7 int n; 8 int k[MAXN]; 9 LL summ; 10 LL ave; 11 LL s[MAXN<<1]; 12 LL ans; 13 14 int main() 15 { 16 ios::sync_with_stdio(false); 17 cin.tie(0); 18 19 cin>>n; 20 for(int i = 1;i <= n;i++) cin>>k[i],summ += k[i]; 21 ave = summ / n; 22 for(int i = 1;i <= n;i++) k[i] -= ave,k[i] += k[i-1]; 23 sort(k+1,k+n+1); 24 int mid = (n + 1) / 2; 25 for(int i = 1;i <= n;i++) 26 { 27 ans += abs(k[i] - k[mid]); 28 } 29 cout<<ans<<'\n'; 30 return 0; 31 }
其实这道题在算法进阶指南上讲的很清楚，不过是自己再手写一遍加深记忆
