题解：P10922 Happybob's Numbers (UBC001B)

主要思路：贪心，构造。

思路

构造题，首先明确要删的就是小于 \(n\) 的数，因为若删了大于等于 \(n\) 的数就无法进行之后的操作了。

那这道题就简单了，先从大到小排序，遇到小于当前长度 \(k\) 的数，就将这个数删掉，这时长度需减 \(1\)，毕竟顺序可以自己调，将下一个小于当前 \(k\) 的数，放到下一个需要删的位置。

但若不是全部删除，需要加 \(1\)，毕竟最后还可以删 \(1\) 个数。

AC Code

#include<bits/stdc++.h>
using namespace std;
int t, n, a[500004];
bool cmp(int x, int y) {
	return x > y;
}
int main() {
	cin >> t;
	while (t--) {
		cin >> n;
		int ans = 0, k = n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		sort(a + 1, a + 1 + n, cmp);
		for (int i = 1; i <= n; i++) {
			if(a[i]<k)ans++,k--;
		}
		if (ans == n)--ans;
		cout << ans + 1 << "\n";
	}
	return 0;
}