正題

題目鏈接:https://www.luogu.org/problemnew/show/P2514

---

題目大意

有一個廠，需要$b$噸煤炭，然后第$j$個礦運到該廠的運費為$c_{0,j}$，運行總費用為運費之和加上$h_0$

現在在$1～n$挑選一個建一個新廠，其余的煤礦都運到這個廠，第$j$個礦運到該廠的運費為$c_{i,j}$，運行費用為運費之和加上$h_i$

求最小費用。

---

解題思路

很簡單的一道貪心題，顯然我們將最優的$b$噸運到舊廠。

我們枚舉建立在哪個廠，然后對于每個礦將$c_{0,j}?c_{i,j}$進行從小到大排序，然后將最小的$b$噸運入舊廠就行了。

---

$code$

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N=55,M=55000; struct node{int w,num; }d[M]; int m,b,H,n,a[M],h[N],c[N][M],ans,mins=2147483647,p; bool cmp(node x,node y) {return x.w<y.w;} int main() {scanf("%d%d%d%d",&m,&b,&H,&n);for(int i=1;i<=m;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&h[i]);for(int i=0;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&c[i][j]);for(int i=1;i<=n;i++){ans=H+h[i];for(int j=1;j<=m;j++)d[j]=(node){c[0][j]-c[i][j],a[j]},ans+=c[i][j]*a[j];sort(d+1,d+1+m,cmp);int k=b;for(int j=1;j<=m&&k;j++)if(k>=d[j].num)k-=d[j].num,ans+=d[j].w*d[j].num;else if(k<d[j].num)ans+=k*d[j].w,k=0;if(ans<mins)mins=ans,p=i;}printf("%d\n%d",p,mins); }

總結

以上是生活随笔為你收集整理的P2514-[HAOI2010]工厂选址【贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。