题目链接
题目解法
这题看起来很 \(flow\)，不难想到边数 \(nm\) 的建图方法：
具体来说，边为 \((S,i,c_i)(i\in [1,m])\)，\((i,j,b_i)(i\in [1,m],\;j\in [1,n])\)，\((j,T,a_i)(j\in [1,n]\)
考虑把最大流按照最小割的方式理解
假设选的零食有 \(x\) 个
对于每个小孩，要么 \(c_i\) 被割了，要么其他 \(n-x\) 个都要割 \(b_i\)
将 \(a\) 从小到大排序，令 \(suma\) 为 \(a\) 的前缀和
所以答案为 \(\min\limits_{i=0}^n suma_{n-i}+\sum\limits_{j=1}^{m}\min\{c_j,i\times b_j\}\)
后面的式子不难优化
时间复杂度 \(O(n\log n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
#define b first
#define c second
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
FF=0;int RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
FF*=RR;
}
typedef pair<int,LL> pil;
const int N=200100;
int n,m;
LL a[N],suma[N],sumc[N],sumb[N];
pil v[N];
int main(){
read(n),read(m);
F(i,1,n) read(a[i]);
sort(a+1,a+n+1);
F(i,1,n) suma[i]=suma[i-1]+a[i];
F(i,1,m) read(v[i].b);
F(i,1,m) read(v[i].c);
sort(v+1,v+m+1,[&](pil x,pil y){ return (__int128)x.c*y.b<(__int128)y.c*x.b;});
F(i,1,m) sumc[i]=sumc[i-1]+v[i].c;
DF(i,m,1) sumb[i]=sumb[i+1]+v[i].b;
LL ans=2e18;int j=0;
F(i,0,n){
while(j+1<=n&&1ll*i*v[j+1].b>=v[j+1].c) j++;
chkmin(ans,suma[n-i]+sumc[j]+sumb[j+1]*i);
}
printf("%lld\n",ans);
return 0;
}