CF1342 D - Multiple Testcases

D - Multiple Testcases

Question

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

Solution

分组记入不同 $m\left[i\right]$m[i]的贡献值，求一个后缀和 $cnt\left[i\right]$cnt[i]表示 $\ge i$≥i的数有多少个。
首先考虑最小分组 $ans$ans， $ans=max\lceil \frac{cnt\left[i\right]}{c\left[i\right]}\rceil$ans=max ⌈c[i]cnt[i]​⌉
接着分组组数确定了，我们只要构造每组都满足题意尽可能多即可。
这里将 $m\left[i\right]$m[i]数组排序，以组数 $ans$ans为周期放入不同的 $vector$vector数组中即可。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;

int n,k,ans,c[N],m[N],cnt[N];
vector<int>G[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>m[i];
		cnt[m[i]]++;
	}
	for(int i=1;i<=k;i++) cin>>c[i];
	for(int i=k;i>=1;i--) cnt[i]+=cnt[i+1],ans=max(ans,(cnt[i]+c[i]-1)/c[i]);
	sort(m+1,m+1+n);
	for(int i=1;i<=n;i++) G[i%ans].emplace_back(m[i]);
	cout<<ans<<'\n';
	for(int i=0;i<ans;i++){
		cout<<G[i].size();
		for(auto t:G[i]) cout<<" "<<t;
		cout<<'\n';
	}
	return 0;
}