题意:一个长为 n (1?≤?n?≤?10^5)的序列(元素(|ai|?≤?10^4) ),可以取其中的两个数,一个数 + 1,另一个数就 - 1,可以这样操作无数次,问最后最多能有多少个数是一样的。
题目链接:http://codeforces.com/problemset/problem/246/B
——>>我觉得非常不错的题目,至少我被坑得团团转。。
第一种惯性思维:尽量地往平均数靠,答案为 n - 余数。。可惜,是错的。。
第二种惯性改进思维:尽量地往平均数靠,答案为 max(n - 余数, 余数)。。可惜,还是错的。。
贪心正解:无论数有多大,我都可以让 n - 1 个数变成 1,让第 n 个数独树一帜。。所以,答案的最小值为 n - 1。。
当总和能被 n 整除,可以平分 n 数时,答案为 n 。。
#include <cstdio>int main()
{int n, a;while (scanf("%d", &n) == 1){int sum = 0;for (int i = 1; i <= n; ++i){scanf("%d", &a);sum += a;}sum % n == 0 ? printf("%d\n", n) : printf("%d\n", n - 1);}return 0;
}