Codeforces1355BYoungExplorers(贪心)

给你n个人, 你需要给这些人组队.

每个人有个对应的ai值, 表示这个人如果组队了, 队伍应当人数>&＃61;ai.

问: 最多能组出多少个队伍. (有些人可以没有队伍)

解题思路

贪心 &＃43; 排序

我们把所有的人按照ai的值从小到大排序.

然后从前向后遍历排序后的数组, 并记录一个sum值, 表示当前已经遍历过, 且没有队伍的人数. 如果sum &＃61;&＃61; a[i], 则表示我们可以让这sum个人组成队伍.

关于思路正确性:

我们目的是成尽可能多的队伍, 所以若能成队伍, 我们直接组成队伍一定是最优的, 而a[i]小的人会先成队.
因此我们排序后从前向后遍历, 一定可能保证成队最多.

关于sum &＃61;&＃61; a[i]时, 一定可以成队:

这也是显然的, 因为a数组小到大排序, 此时sum &＃61;&＃61; a[i], 表示排序后第i个人满足了要求, 则它前面的sum - 1个人也必然满足要求.

AC代码

#include
#define rep(i, n) for (int i &＃61; 1; i <&＃61; (n); &＃43;&＃43;i)
using namespace std;
typedef long long ll;
const int N &＃61; 2E5 &＃43; 10;
int a[N];
int main()
{int t; cin >> t;while (t--) {int n; scanf("%d", &n);rep(i, n) scanf("%d", &a[i]);sort(a &＃43; 1, a &＃43; 1 &＃43; n);int res &＃61; 0, all &＃61; 0;rep(i, n) {all&＃43;&＃43;;if (all &＃61;&＃61; a[i]) all -&＃61; a[i], res&＃43;&＃43;;}printf("%d\n", res);}return 0;
}


END