HDU5353 – Average(模拟递推)

Average

【题意】一堆小朋友围成一个圈，第i和小朋友有ai颗糖果，每个小朋友最多给他左右两边的一次且一颗糖果，可以不给，求最后能否使所有小朋友的糖果数量一样。

【分析】首先所有糖果总数要能除尽n，否则必然不能平分，然后求出平均数，让所有糖果减去平均数，最后目标使得所有ai为0，只要第一个小朋友的操作确定，就能递推出所有小朋友的糖果数量，如果当前a[i] = 1,则必须要给一颗糖果给i+1，如果a[i]=-1,则说明此时先借用了右边的某个糖果，所以需要把i+1的一颗给i；则操作完如果某个a[i]的绝对值超过1(2也不行，因为不能给右边的两个，而左边的已经为0，也不能给)就返回不可能；需要注意n为1的时候以及所有糖果总数为0不能给糖果，直接YES。又无耻的用了输入输出挂。

【AC CODE】109ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXBUF = 10000, MAXOUT = 10000, MAXN = 100000+10;
char buf[MAXBUF], *ps = buf, *pe = buf+1;
inline void rnext(){
	if(++ps == pe)
		pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);
}
template <class T>
inline bool in(T &ans)
{
	ans = 0;
	T f = 1;
	if(ps == pe) return false;//EOF
	do{
		rnext();
		if('-' == *ps) f = -1;
	}while(!isdigit(*ps) && ps != pe);
	if(ps == pe) return false;//EOF
	do
	{
		ans = (ans<<1)+(ans<<3)+*ps-48;
		rnext();
	}while(isdigit(*ps) && ps != pe);
	ans *= f;
	return true;
}
char bufout[MAXOUT], outtmp[50],*pout = bufout, *pend = bufout+MAXOUT;
inline void write()
{
	fwrite(bufout,sizeof(char),pout-bufout,stdout);
	pout = bufout;
}
inline void out_char(char c){ *(pout++) = c;if(pout == pend) write();}
inline void out_str(char *s)
{
	while(*s)
	{
		*(pout++) = *(s++);
		if(pout == pend) write();
	}
}
template <class T>
inline void out_int(T x) {
	if(!x)
	{
		out_char('0');
		return;
	}
	if(x < 0) x = -x,out_char('-');
	int len = 0;
	while(x)
	{
		outtmp[len++] = x%10+48;
		x /= 10;
	}
	outtmp[len] = 0;
	for(int i = 0, j = len-1; i < j; i++,j--) swap(outtmp[i],outtmp[j]);
	out_str(outtmp);
}
int a[MAXN],b[MAXN],n,tol;
LL sum;
P ans[MAXN];

bool ok(int v)
{
	tol = 0;
	memcpy(b,a,sizeof(int)*n);
	b[0] -= v;
	b[1] += v;
	if(-1 == v) ans[tol++] = {1,0};
	else if(1 == v) ans[tol++] = {0,1};
	rep(i,1,n)
	{
		int nxt = (i+1)%n;
		if(b[i] == 1)
		{
			b[nxt]++;
			ans[tol++] = {i,nxt};
		}
		else if(b[i] == -1)
		{
			b[nxt]--;
			ans[tol++] = {nxt,i};
		}
		if(abs(b[nxt]) > 1) return false;
	}
	return true;
}
bool all_zero()
{
	rep(i,0,n) if(a[i]) return false;
	return true;
}
bool sloved()
{
	if(1 == n)
	{
		tol = 0;
		return true;
	}
	if(sum%n) return false;
	int avg = sum/n;
	rep(i,0,n) a[i] -= avg;
	if(all_zero())
	{
		tol = 0;
		return true;
	}
	if(ok(-1) || ok(0) || ok(1)) return true;
	return false;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	in(t);
	while(t--)
	{
		sum = 0;
		in(n);
		rep(i,0,n) in(a[i]), sum += a[i];
		if(!sloved()) out_str("NO\n");
		else
		{
			out_str("YES\n");
			out_int(tol),out_char('\n');
			rep(i,0,tol) out_int(ans[i].first+1),out_char(' '),out_int(ans[i].second+1),out_char('\n');
		}
	}
	write();
	return 0;
}