题目:
Fred likes to wear mismatched socks. This sometimes means he has to plan ahead.
Suppose his sock drawer has 1 red, 1 blue, and 2 green socks. If he wears the red with the blue, he is stuck with matching green socks the next day. Given the contents of his sock drawer, how many pairs of mismatched socks can he put together?
Input
The first line of input contains a single integer n (1 ≤ n ≤ 1,000), the number of different colors of socks in Fred’s drawer. The ith of the next n lines contains a single integer ki (1 ≤ ki ≤ 109), the number of socks of the ith color.
Output
Print, on a single line, the maximum number of mismatched pairs of socks that Fred can make with the contents of his sock drawer.
| 样例输入 | 样例输出 |
|---|
| 3 1 2 1 | 2 |
| 5 1 2 1 10 3 | 7 |
题意: 给你n种个数为ai袜子的袜子，求最多能有多少对袜子颜色不相同.
思路: 贪心题，我们可以先优先着手最大的袜子数，如果最大的袜子数>=其他袜子的数之和，那么显然此时的结果一定为其他袜子的数之和。反之如果最大的袜子数<其他袜子的数之和，则说明每个袜子的个数都是小于sum/2的，从结果最大的方向考虑，我们肯定想要的结果应该尽可能更大。
那么，大到什么程度呢？
答案显然是sum/2，因为我们最多只有sum支袜子.而我们上面讨论的那种情况已经限制所有袜子的个数是小于sum/2的，那我们不妨把每个袜子依次排序，种类相同的放一起，我们每次取当前袜子和该位置往后移动sum/2位置的袜子，这样不仅可以保证袜子的种类不相同(因为每种袜子数量都小于sum/2)，同时也能让结果往sum/2方向趋近。
如果读者了解了上面的意思的话，就会发现，结果一定是sum/2。
上述sum均是偶数条件下，但sum为奇数时同样适用.
AC代码:
#include <iostream>
using namespace std;
long long n;
long long a;
int main() {
cin>>n;
long long sum=0,maxs = 0;
for(int i=0;i<n;i++) {
cin>>a;
sum+=a;
maxs = max(a,maxs);
}
if(sum<=maxs*2) cout<<min(sum-maxs,maxs)<<endl;
else {
cout<<sum/2<<endl;
}
return 0;
}
这题是看大佬的题解思路AC的，觉得很厉害就想自己写写.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
