2426: [HAOI2010]工厂选址

链接

代码：

 /*

 贪心：

     奇妙！！！！！

     因为所有的煤矿不是给新厂，就是给旧厂（而且旧厂的得到b）

     为了使费用最小，感性的理解，那么一个煤矿给哪个厂，取决于到哪个厂近。

     所以开始假设所有的煤都给了新厂，然后取出b的给旧厂，取哪个煤矿呢？

     当然是这个煤矿给了旧厂的费用比给了新厂的费用少（c[0][i]-c[x][i]），所以按照这个排序，依次取出。

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 #define rep(i,a,b) for(int i=(a); i<=(b); ++i)

 #define pa pair<int,int>

 const int M = ; // 煤矿

 const int N = ; // 发电厂

 int a[M],c[N][M],h[N];

 int m,b,n,ans1,ans2 = 1e9;

 pa T[M];

 void solve(int x) {

     int Cost = h[] + h[x], B = b;

     rep (i,,m) {

         Cost += c[x][i] * a[i];

         T[i].first = (c[][i]-c[x][i]);

         T[i].second = i;

     }

     sort(T+,T+m+);

     rep (i,,m) { //--m,1

         int j = T[i].second;

         if (B >= a[j]) {

             Cost += T[i].first * a[j]; // -- Cost-=...

             B -= a[j];

         }

         else {

             Cost += T[i].first * B;

             break;

         }

     }

     if (Cost < ans2)

         ans2 = Cost,ans1 = x;

 }

 int main() {

     m = read(),b = read(),h[] = read(),n = read();

     rep (i,,m) a[i] = read();

     rep (i,,n) h[i] = read();

     rep (i,,n) rep (j,,m) c[i][j] = read(); // -- rep(i,1,n)

     rep (i,,n) solve(i); // -- rep(i,0,n)

     cout << ans1 << "\n"  << ans2;

     return ;

 }