本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-03 16:16:12

以下设 $\sum a_i=s$，同时认为 $n,m,s$ 同级。

首先发现盒子和饼干之间是类似匹配的关系，因此我们以盒子为左部点，每种饼干为右部点，连边即为完全二分图，代表每种饼干只能装到每个盒子中一个。题目所求即为最少的左部点数量使得该图有完美匹配，输出方案。

完美匹配考虑霍尔定理，首先要 $\sum b=\sum a$，然后要求对于所有左部点集合 $S$，都满足 $\sum_{i\in S}b_i\le\sum_{j=1}^n\min(a_j,\left|S\right|)$，这里要对 $a_j$ 取最小值是因为这种饼干最多只能贡献 $a_j$ 的出度。

我们注意到等式右边的取值只与集合大小有关，可以对 $a$ 排序后预处理固定集合大小下的上界 $c$。此时只要 $b$ 最大的若干个的和不超过上界，则更小的一定也不超过，必然合法。问题转化为在 $b$ 中可重复地选尽可能少的数，要求和为 $s$，同时保证前 $i$ 大之和不超过 $c_i$。

直接使用背包，先对 $b$ 排序，设 $f_{i,j,k}$ 表示考虑了前 $i$ 大的 $b$，选了 $j$ 个，总和为 $k$ 是否可行，对所有 $k>c_j$ 的状态强制赋成 $0$ 即可保证限制，转移是完全背包，为 $f_{i,j,k}=f_{i-1,j,k} \ee f_{i,j-1,k-b_i}$，这样就是 $O(n^3)$ 的。

但是我们注意到在 $f_{i,j,k}$ 中使用的 $b$ 至少是 $b_i$，因此 $j\le \lfloor\frac s {b_i}\rfloor$。又因为 $b_i$ 两两不同，所以所有 $j$ 的个数和不超过 $O(n\ln n)$，复杂度降为 $O(n^2\ln n)$。又注意到 DP 值是 $0$ 或 $1$，同时 $f_{i,j}$ 只会从 $f_{i-1,j}$ 和 $f_{i,j-1}$ 在 $k$ 这一维以相同的偏移量转移，因此可以把 $f_{i,j}$ 在 $k$ 这一维的 $s$ 个状态压到 bitset 里优化转移，最终复杂度为 $O(\frac{n^2\ln n}w)$。

至于输出方案，先在 DP 数组上倒着把 $b$ 的方案找出来，然后每次贪心地把 $a$ 最大的若干种各放一个在该盒子里并减 $1$，用堆维护这个过程即可，具体看下面代码。值得一提的是，如果没有方案要求，上面的 DP 其实是可以滚动数组优化的。

#include<iostream>
#include<algorithm>
#include<bitset>
#include<queue>
#define bs bitset <N>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=15000+10;
int n,m,s,r=-1,a[N],b[N],p[N],c[N],w[N];
bool cmpa(int x,int y) {return a[x]<a[y];}
bool cmp(int x,int y) {return x>y;}
bs lm[N];
vector <bs> f[N];
vector <pii> tv;
priority_queue <pii> q;
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],s+=a[i],p[i]=i;
	cin>>m;
	for(int i=1;i<=m;i++) cin>>b[i];
	sort(p+1,p+1+n,cmpa),sort(b+1,b+1+m,cmp);
	int tp=0,ts=0;
	for(int i=1;i<=s;i++)
	{
		while(tp<n&&a[p[tp+1]]<=i) tp++,ts+=a[p[tp]];
		c[i]=ts+(n-tp)*i;
	}
	b[0]=s+1,lm[0][0]=1;
	for(int i=1;i<=s;i++) lm[i]=lm[i-1],lm[i][i]=1;
	for(int i=0;i<=m;i++) f[i].resize(s\/b[i]+1);
	f[0][0][0]=1;
	for(int i=1;i<=m;i++) for(int j=0;j<=s\/b[i];j++)
	{
		if(j<=s\/b[i-1]) f[i][j]=f[i-1][j];
		if(j) f[i][j]|=(f[i][j-1]<<b[i]);
		f[i][j]&=lm[c[j]];
	}
	for(int i=1;i<=s\/b[m];i++) if(f[m][i][s]) {r=i; break;}
	cout<<r<<'\n';
	if(r==-1) return 0;
	int cur=s,tw=m;
	for(int i=1;i<=r;i++) for(int j=tw;j>=1;j--) 
		if(f[j][r-i+1][cur]&&f[j][r-i][cur-b[j]])
			{w[i]=b[j],cur-=b[j],tw=j; break;}
	for(int i=1;i<=n;i++) q.push({a[i],i});
	for(int i=1;i<=r;i++)
	{
		cout<<w[i]<<' ',tv.clear();
		for(int j=0;j<w[i];j++)
		{
			pii te=q.top(); q.pop();
			te.fi--,cout<<te.se<<' ';
			if(te.fi) tv.push_back(te);
		}
		for(pii te:tv) q.push(te);
		cout<<'\n';
	}
	return 0;
}