首页 > 其他 > 详细

BZOJ 2426 [HAOI2010]工厂选址 【贪心】

时间:2018-08-19 12:47:28      阅读:145      评论:0      收藏:0      [点我收藏+]

BZOJ 2426 [HAOI2010]工厂选址

Description

某地区有m座煤矿,其中第i号矿每年产量为ai吨,现有火力发电厂一个,每年需用煤b吨,每年运行的固定费用(包括折旧费,不包括煤的运费)为h元,每吨原煤从第i号矿运到原有发电厂的运费为Ci0(i=1,2,…,m)。

 

现规划新建一个发电厂,m座煤矿每年开采的原煤将全部供给这两座发电厂。现有n个备选的厂址。若在第j号备选厂址建新厂,每年运行的固定费用为hj元。每吨原煤从第i号矿运到j号备选厂址的运费为Cij(i=1,2,…,m;j=1,2,…,n)。

 

试问:应把新厂厂址选取在何处?m座煤矿开采的原煤应如何分配给两个发电厂,才能使每年的总费用(发电厂运行费用与原煤运费之和)为最小。 

 

Input

第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

 

Output

第1行:新厂址编号,如果有多个编号满足要求,输出最小的。

第2行:总费用 

 

Sample Input

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
 

Sample Output

8
49
 

HINT

对于所有数据, n<=50, m<=50000, b<=10000 

 

题解:

贪心好题,想了好久。。。

枚举新工厂,先假设所有的煤全部转移到新工厂了,然后对于每个煤矿厂,记录把煤运到新工厂,和把煤运到旧工厂的成本差,从小到大排序,再一直往旧厂里加加加,一直加到满 B 为止。

计算总成本,更新答案即可。

 

代码如下:

技术分享图片
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=50005;
 4 const int inf=1e9;
 5 int n,m,b,H;
 6 struct node{
 7     int pos,num,cha;
 8 }c3[N];
 9 int c1[N],c2[55][N],a[N],h[55],ans1,ans=inf;
10 inline bool cmp(node a,node b)
11 {
12     return a.cha<b.cha;
13 }
14 inline void doing(int pos)
15 {
16     int cost=h[pos]+H;
17     for (int i=1; i<=m; i++)
18     {
19         cost+=a[i]*c2[pos][i];
20         c3[i].cha=c1[i]-c2[pos][i];
21         c3[i].pos=i;
22     }
23     sort(c3+1,c3+1+m,cmp);
24     int tmp=b;
25     for (int i=1; i<=m; i++)
26       if (tmp)
27       {
28           if (tmp>=a[c3[i].pos])
29           {
30               cost+=a[c3[i].pos]*c3[i].cha;
31               tmp-=a[c3[i].pos];
32         }
33         else cost+=tmp*c3[i].cha,tmp=0;
34       }
35       else break;
36     if (cost < ans)
37     {
38         ans1=pos; ans=cost;
39     }
40 }
41 int main()
42 {
43     scanf("%d%d%d%d",&m,&b,&H,&n);
44     for (int i=1; i<=m; i++)
45       scanf("%d",&a[i]);
46     for (int i=1; i<=n; i++)
47       scanf("%d",&h[i]);
48     for (int i=1; i<=m; i++)
49       scanf("%d",&c1[i]);
50     for (int i=1; i<=n; i++)
51       for (int j=1; j<=m; j++)
52         scanf("%d",&c2[i][j]);
53     for (int i=1; i<=n; i++)
54       doing(i);
55     printf("%d\n%d\n",ans1,ans);
56     return 0;
57 }
View Code

 

 

 

 

加油加油加油!!!fighting fighting fighting!!!

BZOJ 2426 [HAOI2010]工厂选址 【贪心】

原文:https://www.cnblogs.com/Frank-King/p/9500713.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!