题目限制
1500 ms 128 M
题目描述
在克哈星系的冒险中，Jim和他的游骑兵遭遇了虫群的进攻。Jim出色的指挥能力使他在兵力严重不
足的情况下依旧抗击虫群的多次进攻。但与此同时Jim的部分士兵战斗服能源却不足以支持他们继
续作战。为了更强的火力压制，Jim决定将所有士兵的能源平分，以便所有人都能够参与作战。
已知Jim现在有n个枪兵，Jim将n个士兵围成一个圆，所有士兵的能量总和是n的倍数，且每次传输
只能传输1单位的能量。更糟糕的是，充电线的长度是固定的，也就意味着，每次只能让相隔k位
的两人能量交换。
休伯利安号从轨道降落需要非常长的时间，Jim希望在在最快的时间知道最少传输次数。
输入格式
第一行为两个正整数 n,k 表示共n个枪兵。(n<=500000,k<=n)
第二行包含n个正整数val[1]-val[n]，代表每个枪兵的能量 ( val[i]<=1e8)
保证最终结果可以用64位整型储存
输出格式
输出最少的传输次数。数据均保证能够平均分配所有能量。
数据范围
对于 25%的数据 保证 n<=10;
对于 50%的数据 保证 n<=2000
对于 100%的数据 保证 n<=500000
输入样例
4 1
1 3 9 7
输出样例
6
样例解释
比如现在有四个人能量分别为 1 3 9 7 每次使相邻1位的两人能量交换
[1,3,9,7]→[5,3,5,7] (四次)
[5,3,5,7]→[5,5,5,5] (两次)
答案为 6次
将整个环分成多个环单独做一个经典的传递糖果的模型
https://blog.csdn.net/weixin_34238642/article/details/94200423
这个模型我没写过 ， 当时一下子想到了另一个类似的经典问题，我成功的打对了我幻想的那道题。。。。。
手测发现哪里不对赶紧转暴力。。。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int N=500005; 5 int n,k,val[N]; bool vis[N]; 6 int m; long long ans,a[N],b[N],sum[N]; 7 inline long long hehe() 8 {long long aver=0; 9 for(int i=1;i<=m;i++) aver+=a[i]; 10 aver/=m; 11 12 for(int i=1;i<m;i++) b[i]=aver-a[i+1],sum[i]=sum[i-1]+b[i]; 13 14 sum[m]=0; 15 sort(sum+1,sum+m+1); // 1--m 16 long long x=sum[(m+1)/2],re=0; 17 for(int i=1;i<=m;i++) re+=abs(x-sum[i]); 18 19 return re; 20 } 21 int main() 22 { 23 scanf("%d%d",&n,&k); 24 for(int i=1;i<=n;i++) scanf("%d",&val[i]); 25 26 for(int i=1;i<=n;i++) 27 {if(vis[i]) continue; 28 m=0; 29 for(int j=i;;j=(j+k)%n+1) 30 {if(vis[j]) break; 31 vis[j]=1; a[++m]=val[j]; //printf("%lld ",a[m]); 32 } 33 //printf("\n"); 34 ans+=hehe(); 35 } 36 printf("%lld",ans); 37 return 0; 38 }
原文：https://www.cnblogs.com/YuXiaoze/p/11827423.html