本文共 1431 字，大约阅读时间需要 4 分钟。
设第i个人给了第i+1个人mi个糖果(可以为负)，因为最后每个人的糖果都会变成sum/n。
可以得到方程组 mi-mi+1=a[i+1]-sum/n.(1<=i<=n).
把方程组化为mn组成的形式，最后的结果就是求min(abs(mn)+abs(mn-a[i+1]+sum/n)....)。可以看出这是一个分段函数。
且函数最值在mn取中位数的地方。
# include # include # include # include # include # include # include # include # include # include # include using namespace std;# define lowbit(x) ((x)&(-x))# define pi acos(-1.0)# define eps 1e-3# define MOD 1000000007# define INF (LL)1<<60# define mem(a,b) memset(a,b,sizeof(a))# define FOR(i,a,n) for(int i=a; i<=n; ++i)# define FO(i,a,n) for(int i=a; i PII;typedef vector VI;# pragma comment(linker, "/STACK:1024000000,1024000000")typedef long long LL;int Scan() { int res=0, flag=0; char ch; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch-'0'); return flag?-res:res;}void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0');}const int N=1000005;//Code begin... int a[N], b[N];LL sum[N]; int main(){ int n; LL ave=0, ans=0; scanf("%d",&n); FOR(i,1,n) scanf("%d",a+i), ave+=a[i]; ave/=n; FOR(i,1,n) a[i]-=ave; FOR(i,1,n) sum[i]=a[i]+sum[i-1]; sort(sum+1,sum+n+1); LL t=sum[(1+n)>>1]; FOR(i,1,n) ans+=abs(t-sum[i]); printf("%lld\n",ans); return 0;}
转载于:https://www.cnblogs.com/lishiyao/p/6494907.html
