A. Drinks Choosing

A. Drinks Choosing

A. Drinks Choosing

题目大意是输入n和k,n是学生的数量,k是饮料种类,接下来的n行会输入每个学生想要的饮料的编号(1~k),分配饮料是按一对一对分,每一对都是类型相同的饮料,要去输出能得到自己想要

饮料的最大学生数量

 

首先定义两种类别,一种是goods类别,比如两个人都想要第1种饮料,那他们就可以被归类为goods,只有某一个人要这种饮料,他就被归到bads里面

这样一来,goods组里面的人都是满足了需求的人,bads组里面每一对只有一个人满足了需求,所以bads组里满足需求的人数是bads/2向上取整

程序一开始先将对每个种类的需求量记录下来,然后遍历这些记录,将每次的记录模2,模2的结果加到bads里面,接着将记录除2再乘2(直接乘2会包含那个在bads里面的人),将结果加到goods

最后答案就是 bads/2向上取整 + goods

#include<bits/stdc++.h>
using namespace std;

int main(){
  ios::sync_with_stdio(false);
  int n, k, temp;
  cin >> n >> k;
  map<int, int> cnt;

  for(int i=0; i<n; i++){
    cin >> temp;
    cnt[temp]++;
  }

  int goods;
  int bads;
  int ans;
  ans = goods = bads = 0;
  for(auto it: cnt){
    bads += it.second % 2;
    goods += it.second/2 * 2;
  }
  ans = goods + (bads+1)/2;
  cout << ans << endl;
  return 0;
}

 

上一篇:HDU Corn Fields


下一篇:I.Algorithm Choosing Mushrooms