Codeforces Round #725 (Div. 3)B. Friends and Candies
给一个n个数字的数组, 问最少可以取多少个数字, 使得分配给别的数字(包括自己),后让数组的值全相等.
一共n个数组, 那么全相等, 肯定就是sum % n == 0 才可能. 不然怎么分都分不出来.
然后因为要分给别的数, 所以只需要找到比sum/n大的数字, 即可., 因为反正这些大数都要分了才能变成sum/n, 是吧…..脑筋急转弯
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
static class TaskB { public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] ary = in.readIntArray(n); Arrays.sort(ary); int sum = 0; for (int a : ary) sum += a; if (sum % n != 0) { out.printLine(-1); return; } int count = 0; int t = 0; for (int i = 0; i < ary.length; i++) { ary[i] -= sum / n; if (ary[i] < 0) t += ary[i]; } for (int i = ary.length - 1; i >= 0; i--) { if (t >= 0) break; t += ary[i]; count++; } out.printLine(count); } } |