[NOIP 2002 提高组] 均分纸牌

知识点

贪心、前缀差额、守恒

解题思路

计算平均张数avg。从左到右维护前i堆比目标总数多出的差额sum。每个非零sum意味着第i与i+1堆之间必须至少发生一次移动，统计这样的边界数。

正确性说明

前i堆只能通过边界(i,i+1)与右侧交换纸牌，其目标差额非零时该边界必被使用，给出下界。沿相邻边把多余流向不足，可先从盈余处供给，按所需净流量使每个非零边界只移动一次；各堆满足守恒，达到下界。故计数即最少次数。

易错点

计算到n-1条边界，最后总差额一定0；某个前缀已平衡时不要增加操作；负差额也是必须移动。

复杂度

时间O(n)，空间O(n)保存输入，额外状态O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;vector<int>a(n);int sum=0;for(int&x:a)cin>>x,sum+=x;int avg=sum/n,carry=0,ans=0;for(int i=0;i<n-1;i++){carry+=a[i]-avg;ans+=carry!=0;}cout<<ans<<'\n';}