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

有2e5个人,把他们分组,每个人有一个数字 E i E_i Ei?, E i E_i Ei?表示第i个人
所在的组至少有 E i E_i Ei?个人,不必每个人都加入组里面,求最多能分多少组

推荐 _heyuhhh_的B站讲题视频 : https://www.bilibili.com/video/BV1Ai4y147Do?p=2
【Codeforces Round #643 (Div. 2) B. Young Explorers】贪心的分组:
从小到大加入组,尝试把第 i i i个人加入组,如果组内人数 c n t + 1 > = E i cnt+1>=E_i cnt+1>=Ei?则上一个组就凑好了,尝试凑下一组

//#define debug #ifdef debug #include #include "/home/majiao/mb.h" #endif#include #include #include #include #include #include #include #include #include #define MAXN ((int)3e5+7) #define ll long long int #define INF (0x7f7f7f7f) #define QAQ (0)using namespace std; #ifdef debug #define show(x...) \ do { \ cout << "\033[31; 1m " << #x << " -> "; \ err(x); \ } while (0) void err() { cout << "\033[39; 0m" << endl; } #endiftemplate void err(T a, A... x) { cout << a << ' '; err(x...); }int n, m, Q, K, a[MAXN]; int main() { #ifdef debug freopen("test", "r", stdin); clock_t stime = clock(); #endif scanf("%d ", &Q); while(Q--) { scanf("%d ", &n); for(int i=1; i<=n; i++) scanf("%d ", a+i); sort(a+1, a+1+n); int ans = 0, cnt = 0; for(int i=1; i<=n; i++) { if(cnt+1 >= a[i]) { ans ++; //凑好了一组 cnt = 0; } else { //当前组人数加一 cnt ++; } } printf("%d\n", ans); }#ifdef debug clock_t etime = clock(); printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC); #endif return 0; }