NC19977. [HAOI2010]工厂选址
描述
输入描述
第1行：m b h n第2行：a1 a2 … am （0 ≤ ai ≤ 500, a1+a2+...+an ≥ b）第3行：h1 h2 … hn （0 ≤ hi ≤ 100）第4行：C10 C20 … Cm0 （0 ≤ Cij ≤ 50）第5行：C11 C21 … Cm1第n+4行：C1n C2n … Cmn
输出描述
第1行：新厂址编号，如果有多个编号满足要求，输出最小的。
第2行：总费用
示例1
输入:
4 2 7 9 3 1 10 3 6 3 7 1 10 2 7 4 9 1 2 4 3 6 6 8 2 4 10 8 4 10 2 9 2 7 6 6 2 9 3 7 1 2 1 6 9 3 1 10 9 4 2 1 8 2 1 3 4
输出:
8 49
C++11(clang++ 3.9) 解法, 执行用时: 252ms, 内存消耗: 11804K, 提交时间: 2020-03-28 23:43:51
#include<bits/stdc++.h>
using namespace std;
int b, m, n, h;
int c[50005][55], cost[55], a[50005];
struct Fact{
int pos, val;
}w[50005];
inline bool comp(const Fact & x, const Fact & y) {return x.val > y.val;}
int main()
{
int sumcost = 0x7fffffff, num, tag, ans;
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", &cost[i]);
for(int i = 1; i <= m; ++ i) scanf("%d", &c[i][0]);
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
scanf("%d", &c[j][i]);
for(int i = 1; i <= n; ++ i)
{
tag = 0, ans = 0;
for(int j = 1; j <= m; ++ j)
{
w[j].val = c[j][i] - c[j][0];
w[j].pos = j;
}
sort(w + 1, w + 1 + m, comp);
int k = 0;
for(;;)
{
++ k;
if(tag + a[w[k].pos] > b)
{
ans += c[w[k].pos][0] * (b - tag);
ans += c[w[k].pos][i] * (a[w[k].pos] - (b - tag));
break;
}
tag += a[w[k].pos];
ans += c[w[k].pos][0] * a[w[k].pos];
}
for(;k <= m;) ++ k, ans += c[w[k].pos][i] * a[w[k].pos];
ans += h + cost[i];
if(sumcost > ans)
{
sumcost = ans;
num = i;
}
}
printf("%d\n%d\n", num, sumcost);
return 0;
}