一如既往地咕
# 题面
某地区有 $m$ 座煤矿,其中第 $i$ 号矿每年产量为 $a_i$ 吨。
有一个旧发电厂,每年需用煤 $b$ 吨(将恰好 $b$ 吨煤运给旧发电厂),每年维护费用为 $h$ 元,每吨原煤从第 $i$ 号矿运到旧发电厂的运费为 $C_{i0}$($i=1,2,\cdots,m$)。
现规划新建一个发电厂,$m$ 座煤矿每年开采的原煤除了供给旧发电厂的 $b$ 吨,其余全部供给新发电厂。现有 $n$ 个备选的厂址。若在第 $j$ 号备选厂址建新厂,每年维护费用为 $h_j$ 元。每吨原煤从第 $i$ 号矿运到 $j$ 号备选厂址的运费为 $C_{ij}$($i=1,2,\cdots,m$;$j=1,2,\cdots,n$)。
求总费用的最小值,以及在该最小费用下,新发电厂的厂址编号最小是多少。
数据规模 $n\le50$,$m\le50000$,$b\le10000$
# 解析
这道题可以直接贪心,但是既然要学带悔贪心,用带悔贪心做也不是不行 awa
$n$ 不大,可以对每个厂址都计算一次“将新发电厂建在该处的最小花费”。于是只需要决策煤的分配。
记 $c_i$ 为每吨煤从煤矿 $i$ 运到旧发电厂的代价,$c_i’$ 为运到新发电厂的代价。
先考虑简单的情况,假如每个煤矿只有一吨煤。
因为旧发电厂必须要 $b$ 吨煤,不妨先随便安排把这 $b$ 吨凑满。
然后剩下的煤直接分配给新发电厂吗?显然是不一定最优的——考虑当前煤矿 $i$ 的一吨煤:
- 如果煤矿 $j$ 的一吨煤供给了旧发电厂;
- 而用煤矿 $i$ 替代煤矿 $j$ 去供给旧发电厂是否会更优?
条件就是 $c_i+c_j’< c_i’+c_j$ 等价于
于是维护当前供给旧发电厂的煤矿的 $c_j-c_j’$ 的大根堆,如果堆顶可以被煤矿 $i$ 替代,则替代。由于替代出的 $j$ 是当前堆中最大的,所以 $j$ 不可能反过来又替代掉堆中其他的煤矿。
但是现在煤矿不止有一吨煤怎么办?于是我们联想到带悔贪心(模拟费用流)的模板题中“每个洞可以容纳多只老鼠”的情况,用堆维护 pair
,维护 $c_j-c_j’$ 的大根堆,以及该类煤有多少吨。
详见代码。
# 源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
| #include<queue> #include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
inline int Rint(int &r){ int b=1, c=getchar(); r=0; while(c<'0' || '9'<c) b=c=='-'?-1:b, c=getchar(); while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'), c=getchar(); return r*=b; } const int N=55, M=5e4+10; typedef pair<int, int> pii;
int m, varB, varH, n; int num[M], aryh[N], aryc[M][2];
int main(){ Rint(m), Rint(varB), Rint(varH), Rint(n); for(int i=1; i<=m; i++) Rint(num[i]); for(int i=1; i<=n; i++) Rint(aryh[i]); for(int i=1; i<=m; i++) Rint(aryc[i][0]); long long anscost=0; int anspos=-1; for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++) Rint(aryc[j][1]); long long total=varH+aryh[i]; int rem=varB; priority_queue<pii, vector<pii>, greater<pii> > que; for(int j=1; j<=m; j++){ int tmp=num[j], use=0; if(rem) if(rem>=tmp){ total+=1ll*aryc[j][0]*tmp; rem-=tmp, use=tmp, tmp=0; } else{ total+=1ll*aryc[j][0]*rem; tmp-=rem, use=rem, rem=0; } while(!que.empty() && tmp){ if(que.top().first>=aryc[j][1]-aryc[j][0]) break; pii tp=que.top(); que.pop(); int now=min(tmp, tp.second); use+=now, tp.second-=now, tmp-=now; if(tp.second) que.push(tp); total+=1ll*now*tp.first+1ll*now*aryc[j][0]; } if(tmp) total+=1ll*tmp*aryc[j][1]; if(use) que.push(make_pair(aryc[j][1]-aryc[j][0], use)); } if(~anspos){ if(total<anscost) anscost=total, anspos=i; } else anscost=total, anspos=i; } printf("%d\n%lld\n", anspos, anscost); return 0; }
|
THE END
Thanks for reading!
> Link 余命3日少女-网易云