链接: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;
}