首页 > 其他 > 详细

POJ 2709

时间:2017-04-17 20:52:25      阅读:290      评论:0      收藏:0      [点我收藏+]

一道比较基础的贪心题,贪心的时候要从两点出发,一个是从剩余的最多的颜料开始合成灰色颜料,另一个就是合成时要1ml1ml的合成。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 bool cmp(int p,int q)
 8 {
 9     return p>q;
10 }
11 
12 int main()
13 {
14     int n;
15     int a[20];
16     int b[20];
17     int t;
18     while(scanf("%d",&n)&&n)
19     {
20         memset(a,0,sizeof(a));
21         memset(b,0,sizeof(b));
22         int sum=0;
23         for(int i=0;i<n;i++)
24             cin>>a[i];
25         cin>>t;
26         sort(a,a+n,cmp);
27         if(a[0]%50==0)//先确定不合成灰色颜料时最少需要多少套颜料
28             sum=a[0]/50;
29         else
30             sum=a[0]/50+1;
31         if(t!=0)//如果需要灰色颜料
32         {
33             for(int i=0;i<n;i++)//将剩余的颜料存起来
34                 b[i]=sum*50-a[i];
35             while(t>0)//判断灰色颜料是否合成够数
36             {
37                 sort(b,b+n,cmp);//每次排序找到最多的三种颜料
38                 if(b[2]!=0)//颜料够就1ml减少
39                 {
40                     t--;
41                     b[0]--;
42                     b[1]--;
43                     b[2]--;
44                 }
45                 else//颜料不够就多加一套
46                 {
47                     sum++;
48                     for(int i=0;i<n;i++)
49                         b[i]+=50;
50                 }
51             }
52         }
53         cout<<sum<<endl;
54     }
55     return 0;
56 }

 

POJ 2709

原文:http://www.cnblogs.com/acceped/p/6724577.html

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