[ARC125E] Snack 题解

· · 题解

题目传送门

思路

神仙网络流题。

将每种零食和每个小孩看成一个点，然后构造一个源点，连向每个零食，流量为每种零食的个数，然后再在零食与小孩之间连边，流量为小孩每种能吃的最大个数。最后构造一个汇点，每个小孩向汇点连边，流量为每个小孩最多可以吃的零食数。

建好图后，可以发现这是个最大流，但由于点数达到了 4 \times\ 10^5，显然直接跑最大流会 T 的飞起，所以要找到一种快速的计算最大流的方法。

由最大流最小割定理可知，最大流等于最小割。恰好，在此题中，最小割较好处理。具体实现方法可以先将 A 数组排序，然后将小朋友按 C 除以 B 由大到小排序，并分别对 B 和 C 数组做前缀和和后缀和（具体用处下面会说）。然后从小到大枚举切断 A 的数量，并对与每个小朋友，选取切断 B 或 C 的最小代价。

如何选取切断的 A 很好办到，难点在于处理 B 和 C，这时候刚才的排序就起作用了。可以再设一个指针 j，从 1 到 j-1 切断 B，剩下的切断 C。显然，由于刚才的排序，j 是单调递增的。所以可以在每次计算之前先移动 j 指针，然后再进行计算。

代码实现

复杂度分析

时间复杂度瓶颈在排序（显然可以用快排），总体时间复杂度线性对数。

AC Code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,a[N],b[N],c[N],s,ans=0x3f3f3f3f3f3f3f3f;
struct node{
    int b,c;
}q[N];
bool cmp(node a,node b){
    return a.c*b.b>b.c*a.b;//将除法改为乘法，精度更高，且速度更快
}//比较函数
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",&q[i].b);
    for(int i=1;i<=m;i++) scanf("%lld",&q[i].c);//输入
    sort(a+1,a+n+1);//将 A 从小到大排序
    sort(q+1,q+m+1,cmp);//将小孩按 C/B 排序
    for(int i=2;i<=n;i++) a[i]+=a[i-1];//做 A 的前缀和
    for(int i=1;i<=m;i++) b[i]=b[i-1]+q[i].b;//做 B 的前缀和
    for(int i=m;i;i--) c[i]=c[i+1]+q[i].c;//做 C 的后缀和
    for(int i=0,j=1;i<=n;i++){
        int res=a[i];//割断 A 的代价
        for(;q[j].b*(n-i)<q[j].c;j++);//移动 j 指针
        res+=(n-i)*b[j-1]+c[j];//总代价
        ans=min(res,ans);//记录最小值
    }//计算最小割
    printf("%lld",ans);//输出
    return 0;
}

完结撒花！