题面
BZOJ https://lydsy.com/JudgeOnline/problem.php?id=2426
洛谷 https://www.luogu.org/problemnew/show/P2514
题解
首先看懂题目到底在做什么.
然而发现我们显然可以对于每个备选位置跑一遍费用流, 然后并不够优秀.
不难发现所有的位置都要分配给两个工厂, 而其中一个工厂的用量是 \(b\). 那么我们先假装把所有的全部分配给这一个工厂, 这样子我们每次把一些分给另外一个工厂的时候, 对于答案的贡献就已知了, 那么从贡献小的往贡献大的贪心即可.
还是记住这样一句话, 我们的贪心过程从某种意义上来说就是在模拟费用流的过程.
这样子的复杂度就是 \(O(nmlog)\) 了.
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- #define ll long long
- #define MAX 50500
- inline int read()
- {
- int x=0;bool t=false;char ch=getchar();
- while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
- if(ch=='-')t=true,ch=getchar();
- while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
- return t?-x:x;
- }
- int m,b,H,n,a[MAX],h[MAX],c[MAX],c0[MAX];
- int ans,sum=2e9;
- int all,p[MAX],v[MAX];
- bool cmp(int a,int b){return v[a]<v[b];}
- int main()
- {
- m=read();b=read();H=read();n=read();
- for(int i=1;i<=m;++i)a[i]=read();
- for(int i=1;i<=m;++i)all+=a[i];
- for(int i=1;i<=n;++i)h[i]=read();
- for(int i=1;i<=m;++i)c0[i]=read();
- for(int i=1;i<=m;++i)p[i]=i;
- for(int i=1;i<=n;++i)
- {
- for(int j=1;j<=m;++j)c[j]=read();
- int tot=H+h[i];
- for(int j=1;j<=m;++j)tot+=c0[j]*a[j];
- for(int j=1;j<=m;++j)v[j]=c[j]-c0[j];
- sort(&p[1],&p[m+1],cmp);
- int ht=all-b;
- for(int j=1;j<=m;++j)
- if(ht>a[p[j]])ht-=a[p[j]],tot+=v[p[j]]*a[p[j]];
- else{tot+=v[p[j]]*ht;break;}
- if(tot<sum)sum=tot,ans=i;
- }
- printf("%d\n%d\n",ans,sum);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2827651.html