均分纸牌

题目分析：

• 多了往右边放，少了从右边取

Code:

#include <bits/stdc++.h>
using namespace std;
#define maxn 110

int n,a[maxn],sum=0,q[maxn];

inline int read_() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}

void readda_() {
	n=read_();
	for(int i=1;i<=n;++i) {
		a[i]=read_();
		sum+=a[i];
	}
	sum/=n;
	int ans=0;
	for(int i=1;i<=n;++i) q[i]=a[i]-sum;
	for(int i=1;i<n;++i) {
		if(q[i]!=0) {
			q[i+1]+=q[i];
			++ans;
		}
	}
	printf("%d",ans);
}

int main() {
	freopen("a.txt","r",stdin);
	readda_();
	return 0;
}

糖果传递

题目分析见训练指南P5

Code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long 
#define maxn 1000010

int n;
LL a[maxn],c[maxn];

void readda_() {
	scanf("%d",&n);
	LL M=0;
	for(int i=1;i<=n;++i) {
		scanf("%lld",&a[i]);
		M+=a[i];
	}
	M/=n;
	c[0]=0;
	for(int i=1;i<n;++i) c[i]=c[i-1]+a[i]-M;
	sort(c,c+n);
	LL pdc=c[n/2],ans=0;
	for(int i=0;i<n;++i) {
		ans+=abs(pdc-c[i]);
	}
	printf("%lld",ans);
}

int main() {
	freopen("a.txt","r",stdin);
	readda_();
	return 0;
}