【网络流，最小割，双指针，观察，性质】[ARC125E] Snack
ZillionX
·
·
题解
Description
有 n 种零食，第 i 种零食有 a_i 个。有 m 个小孩，需要把零食分给小孩们，其中第 i 个小孩任一零食只能拿 \le b_i 个，总共只能拿 \le c_i 个。问最多能分出的零食。
# Solution
这些 $\le x$ 的限制看起来就很线性规划，我们考虑网络流建模。
我们从源点向每个零食连流量为 $a_i$ 的边，每个零食向每个小孩连对应的流量为 $b_i$ 的边，所有小孩向汇点连流量为 $c_i$ 的边。
网络流求解类二分图匹配可以做到 $\mathcal O(m \sqrt n)$，因为 $m$ 太大了，所以显然不可行。
观察到中间有很多冗余边，我们考虑用精妙的方法求出这个特殊问题的最小割。
我们考虑如果零食已经被钦定好了连 $S$ 还是连 $T$，则对于每个小孩，连 $S$ 的代价为 $c_i$，连 $T$ 的代价为 $x b_i$，其中 $x$ 为连 $S$ 的零食数量。
既然小孩的代价只和 $x$ 有关，那么我们直接枚举 $x$ 就好了。肯定是把最小的 $n-x$ 个零食割掉。然后小孩的贡献就是 $\min (c_i,x b_i)$，这个可以按 $\dfrac{c_i}{b_i}$ 排序后双指针维护。
时间复杂度线性对数。
# Code
```cpp
const int N=2e5+5;
int n,m,a[N];
struct dat {
int b,c;
bool operator<(const dat &r) const {
return c*r.b>r.c*b;
}
}v[N];
signed main() {
scanf("%lld%lld",&n,&m);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
for (int i=1;i<=m;i++) scanf("%lld",&v[i].b);
int sa=0,sb=0,sc=0,ans=LLONG_MAX;
for (int i=1;i<=m;i++) scanf("%lld",&v[i].c),sc+=v[i].c;
sort(v+1,v+m+1);
sort(a+1,a+n+1);
for (int i=n,j=1;i>=0;i--) {
sa+=a[n-i];
for (;j<=m && v[j].b*i<=v[j].c;j++) sb+=v[j].b,sc-=v[j].c;
ans=min(ans,sa+sb*i+sc);
}
printf("%lld",ans);
return 0;
}
```