Codeforces Round #643 (Div. 2) B. Young Explorers (思维,贪心)

题意:给你一组人\(a\),现在要将这些人进行分组,对于\(i\),只有某一组的人数\(\ge a_{i}\)时,\(i\)才可以加入这个组,问最多能够有多少组,(不必将所有人都选用).
题解:我们将所有\(a_{i}\)相同的用一个桶存一下,然后升序遍历这个桶,假如桶里面的人数\(\ge a_{i}\),那么它们就能够组成一组,之后我们再取余,将剩下的人记录下来,继续遍历后面的桶,如果这些剩余的人数\(\ge a_{i}\),那么它们也可以组成一组,继续遍历下去就行了.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

using namespace std;

typedef pair<int,int> PII;

typedef pair<long,long> PLL;

int t;

int n,a[N];

map<int,int> mp;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);

    cin>>t;

     while(t--){

         cin>>n;

         mp.clear();

          for(int i=1;i<=n;++i){

              cin>>a[i];

              mp[a[i]]++;

          }

          int cnt=0;

          int rest=0;

          for(auto w:mp){

              cnt+=w.se/w.fi;

              rest+=w.se%w.fi;

              if(rest>=w.fi){

                  cnt+=rest/w.fi;

                  rest=rest%w.fi;

              }

          }

          printf("%d\n",cnt);

     }

    return 0;

}

巴特西

Codeforces Round #643 (Div. 2) B. Young Explorers (思维,贪心)

最新文章

热门文章