p*****2
发帖数: 21240 | 1 有一个整数数组，你可以进行一种操作
取两个元素， A[i], A[j], 进行A[i]++, A[j]--
你可以进行无限次这种操作
问题是，经过你的操作以后，你可以得到的最大数目的元素，使得他们的值相等。
比如
2 1
无论你怎么操作，最大元素数都是 1
1 4 1
最大元素数可以到3
1++
4--
2 3 1
3--
1++
2 2 2 |
b***m
发帖数: 5987 | |
p*****2
发帖数: 21240 | 3
看例子。
【在 b***m 的大作中提到】
: 题意写得不清晰……
|
b***m
发帖数: 5987 | |
l*****a
发帖数: 14598 | 5 才周三
不知道这个周末得上多少道
【在 p*****2 的大作中提到】
: 有一个整数数组，你可以进行一种操作
: 取两个元素， A[i], A[j], 进行A[i]++, A[j]--
: 你可以进行无限次这种操作
: 问题是，经过你的操作以后，你可以得到的最大数目的元素，使得他们的值相等。
: 比如
: 2 1
: 无论你怎么操作，最大元素数都是 1
: 1 4 1
: 最大元素数可以到3
: 1++
|
p*****2
发帖数: 21240 | 6
数组中每一个不是叫元素吗？
【在 b***m 的大作中提到】
: 我能看懂。“元素”这个词很让人迷惑啊。
|
p*****2
发帖数: 21240 | 7
每天三题？
【在 l*****a 的大作中提到】
: 才周三
: 不知道这个周末得上多少道
|
b***m
发帖数: 5987 | |
p*****2
发帖数: 21240 | 9
任意的。
【在 b***m 的大作中提到】
: 任意数组？
|
l*********8
发帖数: 4642 | 10 难道是这样？
int pk2(vector & A)
{
int reminder = std::accumulate(A.begin(), A.end(), 0) % A.size();
return max(A.size()-1, A.size()-reminder);
}
【在 p*****2 的大作中提到】
: 有一个整数数组，你可以进行一种操作
: 取两个元素， A[i], A[j], 进行A[i]++, A[j]--
: 你可以进行无限次这种操作
: 问题是，经过你的操作以后，你可以得到的最大数目的元素，使得他们的值相等。
: 比如
: 2 1
: 无论你怎么操作，最大元素数都是 1
: 1 4 1
: 最大元素数可以到3
: 1++
|
|
|
b***m
发帖数: 5987 | |
Q*******e
发帖数: 939 | |
p*****2
发帖数: 21240 | 13
竞赛题, 属于greedy, math
【在 Q*******e 的大作中提到】
: 看懂了
: 这种题目有实际应用么
|
l*******b
发帖数: 2586 | 14 难道不能盯着一个A[0] 和所有其他的A[i]做一遍，得到除了A[0]以外其他都一样大？
然后应该有简单判别法确定是不是能让A[0]也一样吧 |
l*******b
发帖数: 2586 | 15 对，求和看能不能被元素个数整除就可以了吧
【在 l*******b 的大作中提到】
: 难道不能盯着一个A[0] 和所有其他的A[i]做一遍，得到除了A[0]以外其他都一样大？
: 然后应该有简单判别法确定是不是能让A[0]也一样吧
|
b****e
发帖数: 45 | 16 对每个subset S, 判断是否符合如下条件：
Sum（S）能被Size(S)整除。
然后找出size最大的那个subset应该就是答案了。
证明过程：
假设最后达成相等的所有元素集合为S,其中的元素值为x. 则S中的元素是由一部分初始
值大于等于X的子集(假设为S1)向剩余初始值小于x的子集(假设为S2）进行"重分配"得
到的。因此这样的集合需满足如下条件：
Sum(S1) - |S1|x = |S2|x - Sum(S2)
即：
x = [Sum(S1) + Sum(S2)] / (|S1| + |S2|) = Sum(S) / |S|
结果为整数即可。
【在 p*****2 的大作中提到】
: 有一个整数数组，你可以进行一种操作
: 取两个元素， A[i], A[j], 进行A[i]++, A[j]--
: 你可以进行无限次这种操作
: 问题是，经过你的操作以后，你可以得到的最大数目的元素，使得他们的值相等。
: 比如
: 2 1
: 无论你怎么操作，最大元素数都是 1
: 1 4 1
: 最大元素数可以到3
: 1++
|
b****e
发帖数: 45 | 17 修正一下：根据题目提供的条件，好像结果在N和N-1之间选择就行了，把所有元素加起
来除以元素个数，能整除的话就是N, 否则就是N-1（把第一个元素一直递减直到满足其
他N-1个元素相等就可以了）。
【在 b****e 的大作中提到】
: 对每个subset S, 判断是否符合如下条件：
: Sum（S）能被Size(S)整除。
: 然后找出size最大的那个subset应该就是答案了。
: 证明过程：
: 假设最后达成相等的所有元素集合为S,其中的元素值为x. 则S中的元素是由一部分初始
: 值大于等于X的子集(假设为S1)向剩余初始值小于x的子集(假设为S2）进行"重分配"得
: 到的。因此这样的集合需满足如下条件：
: Sum(S1) - |S1|x = |S2|x - Sum(S2)
: 即：
: x = [Sum(S1) + Sum(S2)] / (|S1| + |S2|) = Sum(S) / |S|
|
l*********8
发帖数: 4642 | 18 agree
【在 b****e 的大作中提到】
: 修正一下：根据题目提供的条件，好像结果在N和N-1之间选择就行了，把所有元素加起
: 来除以元素个数，能整除的话就是N, 否则就是N-1（把第一个元素一直递减直到满足其
: 他N-1个元素相等就可以了）。
|
w***o
发帖数: 109 | 19 完全同意
【在 b****e 的大作中提到】
: 修正一下：根据题目提供的条件，好像结果在N和N-1之间选择就行了，把所有元素加起
: 来除以元素个数，能整除的话就是N, 否则就是N-1（把第一个元素一直递减直到满足其
: 他N-1个元素相等就可以了）。
|
p*****2
发帖数: 21240 | 20
对。
【在 b****e 的大作中提到】
: 修正一下：根据题目提供的条件，好像结果在N和N-1之间选择就行了，把所有元素加起
: 来除以元素个数，能整除的话就是N, 否则就是N-1（把第一个元素一直递减直到满足其
: 他N-1个元素相等就可以了）。
|
m*****k
发帖数: 731 | 21 I am curious why nobody agreed after luckynoob. :-) |
