https://www.luogu.org/problemnew/show/P1031
题目是个水题, 但是我觉得其思想还是很好的
首先是个求平均数, 这个没什么好说的
其次就用了个类似差分的思想, 将离平均数的个数用正负来表示, 正的是需要转移给别人的, 负的是需要被转移的
然后就用了前缀和, 更准确来说用了 dp 的思想 ---- 状态转移, 因为这个数要为正只能被其前面或后面转移而来, 取同一个方向, 就只能是同一个方向转移
- for(int i=1;i<=n;i++){cin>>a[i];ans+=a[i];}
- ans/=n;
- for(int i=1;i<=n;i++)a[i]-=ans;
- for(int i=1;i<=n;i++) if(a[i]) {a[i+1]+=a[i];k++;}
然后只有不为 0 时才不用移动 (因为是同一方向, 具有无后效性, 例如从左到右, 前缀和时有一个为 0 了, 那就说明这个数的多余部分都是给了他前面的 (无后效性!!!!)
然后就很清楚了, 统计一下就行了
来源: http://www.bubuko.com/infodetail-2977323.html