目录
Description
有 \(m\) 座煤矿，每一座煤矿有 \(a_i\) 吨煤，第 \(i\) 座煤矿到第 \(j\) 号发电厂的运费为 \(c_{i,j}\) 每吨。
有一座发电厂（标号为 0），需要恰好 \(b\) 吨煤矿发电，初始运行费用为 \(h\)。还有 \(n\) 座待运行的发电厂（标号为 1~n），每座发电厂初始运行费用为 \(h_i\)，你需要选择其中一座让它运行起来。
将所有煤分给这两座发电厂，问最小费用是多少。
Solution
这道题的题目描述就是第一个坑，注意以下几点：
0号发电站一定要运行，原题面可能有些表述模糊。- 对于新的发电站，它分配到的煤为 \(tot-b\)（其中 \(tot=\sum \limits_{i=1}^m a_i\)）吨，而不是 \(b\) 吨。
发现 \(1\le m\le5\times10^4,1\le n\le50\)，所以遍历 \(n\) 座发电厂，每次遍历所有煤矿，比较选当前的发电厂时的费用是可以过的。
假设当前遍历到 \(i\) 号发电厂，若所有煤都在这个发电厂，费用为 \(\sum\limits_{j=1}^m a_{j}\times c_{j,i}\) 。
因为 0 号发电厂要选 \(b\) 吨，所以费用为 \(\sum\limits_{j=1}^m a_{j}\times c_{j,i}-\sum\limits_{k=1}^t a_k\times(c_{k,i}-c_{k,0})\)（后面的都是转到 0 号去了）。为了最小化费用，所以要让 \(c_{k,i}-c_{k,0}\) 尽量大，按这个值对每一座煤矿进行排序。然后遍历煤矿，如果还加的进 0 号（可能整座煤矿加不进，只加的进一部分，需要判断每次加入前 0 号的剩余空间）就加，加不进就加到 \(i\) 号。
然后比较每一座发电站的费用大小即可。
Code
#include<bits/stdc++.h>
using namespace std;
int m,b,h,n;
int a[50050],w[60],c[60][50050];
struct node{
int no,val;
}d[50050];
bool cmp(node x,node y){
return x.val>y.val;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>m>>b>>h>>n;
for(int i=1;i<=m;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>w[i];
}
for(int i=0;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c[i][j];
}
}
int minn=1000000000,ans=0;
for(int i=1;i<=n;i++){
int tot=0,sum=h+w[i]; //运行费用别忘了
for(int j=1;j<=m;j++){
d[j].no=j;
d[j].val=c[i][j]-c[0][j];
}
sort(d+1,d+1+m,cmp);
int j=1;
for(j;j<=m;j++){
if(b-tot<=a[d[j].no]){ //放不进整座
sum+=(b-tot)*c[0][d[j].no];
sum+=(a[d[j].no]-b+tot)*c[i][d[j].no];
break;
}
sum+=a[d[j].no]*c[0][d[j].no];
tot+=a[d[j].no]; //更新剩余空间
}
j++;
for(j;j<=m;j++){
sum+=a[d[j].no]*c[i][d[j].no];
}
if(sum<minn){
minn=sum;
ans=i;
}
}
cout<<ans<<endl<<minn<<endl;
return 0;
}