链接:http://codeforces.com/contest/1195/problem/A
A. Drinks Choosing
题意:
题目很长,大概意思是有n个人,每个人喜欢一种类型的饮料,可能很多人喜欢同一种饮料,一共有k种饮料。商店卖的饮料一盒两瓶,现在买n/2盒(向上取整),每人一瓶,问最多有多少人能喝到自己喜欢的饮料?
分析:
把喜欢同一种饮料的人归为一类,然后优先给喜欢同一种饮料且是偶数个人发饮料,这样两个人都能喝到自己喜欢的饮料。然后如果还有剩余整盒的(就是两瓶一起),每盒就只能有一个人喝到自己喜欢的了,另一个人肯定是喝不到了。
code:
#include <cstdio>
#include <cstring>
using namespace std;
int num[1000+7];
int main()
{
int n, k;
while(scanf("%d %d", &n, &k) != EOF)
{
memset(num, 0, sizeof(num));
int x;
for(int i=0; i<n; i++)
{
scanf("%d", &x);
num[x] ++ ; // 喜欢相同类型饮料的人数
}
int ans = 0; // 多少个人喝到自己喜欢的饮料
int cnt = (n+1) / 2; // 买的饮料盒数,向上取整
for(int i=1; i<=k; i++) // 遍历喜欢每种饮料的人
{
while(num[i] >= 2 && cnt > 0) // 如果是偶数个人且还有整盒的
{
cnt --;
num[i] -= 2;
ans += 2;
}
}
printf("%d\n", ans += cnt);
}
return 0;
}