P9339 [JOISC 2023] Cookies (Day3) 题解
_fairytale_
·
·
题解
先假装我们知道了盒子有 k 个和对应的容量 c_1\dots c_k，建立一个类似网络流的二分图：对于第 i 种饼干，建边 S\xrightarrow{a_i}i；对于第 i 个盒子，建边 i\xrightarrow{c_i}T；每个饼干向每个盒子连容量为 1 的边。
考虑 Hall 定理，有一种合法方案当且仅当 \sum a=\sum c 并且对于每个盒子集合 S，\sum_{i\in S}c_i\le \sum_{i=1}^n\min(a_i,|S|)，这个取 \min 是因为如果某个 a_i>|S| 的话，这个点集大小是假的，根本不可能。
然后考虑某一个盒子集合 S，把 S 中的所有数换成 c 的前 |S| 大变成 S'，显然 S' 的限制是更强的，即如果 S' 的限制被满足，那么 S 就会被满足，因此在把盒子从大到小排序之后，我们只需满足这个序列每个前缀的限制。
于是转化为，找到存在满足条件的序列 c 的最小长度 k：c 中的元素递减，c_i\in B，对于 c 的每个长 j 的前缀，都要满足 \sum_{i=1}^jc_i\le \sum_{i=1}^n\min(a_i,j)，\sum c=\sum a。
把 B 从大到小排序，设 f_{i,j,k} 表示考虑 B 中前 i 个元素，已经选了 j 个，\sum c=k 是否可行。
f_{i,j,k}\to f_{i,j+1,k+b_i}\\
f_{i,j,k}\to f_{i+1,j,k}
\end{cases}
对于构造方案，首先找出所有箱子的容量 $c_1\dots c_k$，考虑从大往小删除然后归纳，每次让限制尽可能松，发现需要让 $\sum\min(a_i,j)$ 尽可能大，所以每次匹配一些最大的 $a$ 即可。
```cpp
#define maxn 15010
int n,m;
int a[maxn],b[maxn],c[maxn];
vector<bitset<maxn>>f[maxn];
int cf[maxn];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
rep(i,1,n)cin>>a[i];
rep(i,1,n)cf[a[i]+1]+=1;
cin>>m;
rep(i,1,m)cin>>b[i];
int sum=accumulate(a+1,a+n+1,0);
sort(b+1,b+m+1,greater<int>());
f[0].resize(1);
f[0][0][0]=1;
int ans=inf;
bitset<maxn>tmp;
d(sum),ce;
rep(i,1,m) {
int lim=sum/b[i]+1;
f[i].resize(lim+2);
int lst=f[i-1].size();
rep(j,0,lst-1)f[i][j]=f[i-1][j];
int C=n,pre=0;
tmp.reset();tmp[0]=1;
auto &F=f[i];
rep(j,0,lim) {
C-=cf[j+1];
rep(t,pre+1,pre+C)tmp[t]=1;
pre+=C;
F[j+1]|=(F[j]<<b[i]);
F[j+1]&=tmp;
}
rep(j,0,lim+1)if(F[j][sum])ckmin(ans,j);
}
if(ans==inf){
cout<<"-1\n";
return 0;
}
cout<<ans<<'\n';
per(i,m,1){
if((int)f[i].size()>ans&&f[i][ans][sum]){
auto dfs=[&](auto&self,int i,int j,int s)->void{
if(i==0)return;
c[j]=b[i];
if(j>=0&&s>=b[i]&&f[i][j-1][s-b[i]])self(self,i,j-1,s-b[i]);
else self(self,i-1,j,s);
};
dfs(dfs,i,ans,sum);
break;
}
}
priority_queue<pii>p;
rep(i,1,n)p.push({a[i],i});
rep(i,1,ans){
cout<<c[i]<<" ";
vector<pii>vec;
rep(j,1,c[i]){
pii t=p.top();p.pop();
cout<<t.se<<" ";
if(t.fi>1)vec.push_back({t.fi-1,t.se});
}
for(pii t:vec)p.push(t);
cout<<'\n';
}
return 0;
}
```