Change
1s,256M
【题目描述】
给你一个含n个整数的序列A，每次你可以对这个序列做如下操作：
1）选择2个元素ai,aj(i!=j)
2）改变这2个元素的值，也就是ai=ai+1aj=aj-1
你可以对这个序列进行任意次操作，问你最多能得到多少个相同的数？
【输入格式】
第一行n
第二行n个数，为序列A
【输出格式】
一个数为最多能得到相同数的个数
【输入输出样例】
Input1
2 2 1
Output1
1
Input2
3 1 4 1
Output2
3
【数据约定】
100%数据：n<=10^5, |ai|<=10^4
【解法】
第一眼看到题，什么来的，线段数维护区间？后面想想无论怎么操作所有数字的和不变；
所以所有的和是n的倍数答案就是n（刚好平均分配）
如果不是n的倍数答案就是n-1（牺牲一个数，把其他数都变得一样大）
【代码】
#include<cstdio> #include<cstdlib> #include<iostream> #include<iomanip> using namespace std; int i,j,k,m,n,o,p,js,jl,mm; int main() { FILE *fin,*fout; fin=fopen("change.in","rb"); fout=fopen("change.out","wb"); fscanf(fin,"%d",&n); js=0; for(i=1;i<=n;i++) { fscanf(fin,"%d",&jl); if(js>0)js=js+jl; else js=js+n-(0-jl)%n; } m=js%n; if(m==0)fprintf(fout,"%d",n); else fprintf(fout,"%d",n-1); fclose(fin); fclose(fout); return 0; }
