Codeforces 1342 D. Multiple Testcases

题意：

给定 $n$n 个数 $m[i]$m[i]，每个 $m_i$mi​ 都在 $[1,k]$[1,k] 的范围内再给定 $k$k 个数 $c_i$ci​,要求将所有的 $m[i]$m[i] 进行分组, $c_i$ci​ 表示每组中大于等于 $i$i 的数不超过 $c_i$ci​ 个.求最少能分几组，并输出分组方案。

首先要求出最小分组 ，求出数组 $m$m 中大于等于 $i$i 的数字的个数。又因为 $c_i$ci​ 数组表示每个分组大于等于 $i$i 的数字的最大个数。所以就能得到，对于数字 $i$i 而言，最小分组数为 $cnt_i$cnti​ 除以 $c_i$ci​ 向上取整，然后找最大值。

得出最小分组 后
贪心即可，将数组循环放置。

AC代码：

const int N = 2e5 + 10;
int m[N], c[N], cnt[N];
vector<int> v[N];
int n, k;
int ans, res, tmp, maxn;
int main()
{
	sdd(n, k);
	rep(i, 1, n)
	{
		sd(m[i]);
		cnt[m[i]]++; //cnt数组表示等于i的数字个数
	}
	rep(i, 1, k)
		sd(c[i]);
	per(i, k, 1)
	{
		cnt[i] += cnt[i + 1]; //i位置依次加上后面的数量，表示大于等于i的数字个数
		maxn = max(maxn, (cnt[i] + c[i] - 1) / c[i]);
	}
	sort(m + 1, m + 1 + n); //对m数组排序，可选从大到小
	rep(i, 1, n)
	{
		v[i % maxn].push_back(m[i]); //循环放入vector
	}
	pd(maxn);
	rep(i, 0, maxn - 1)
	{
		printf("%d", v[i].size());
		for (int it : v[i])
			printf(" %d", it);
		printf("\n");
	}
	return 0;
}