POJ 2709 Painter 贪心

这题比较犀利,特别的地方是在配灰色的时候。
用judge[]存储减去对应颜色后剩余的体积,用这部分配灰色。当然judge中的每一项都有大于0
配法:每排一次序配1ml,保证这1ml是由体积最多的三种颜料配成。
最初的时候是排序,然后一下配最大的三个当中最小的那个的体积,这是不够贪的。
#include<iostream>
#include
<cstring>
#include
<algorithm>
using namespace std;
int color[13]={0};
int judge[13]={0};
int deal(int n)
{
     
int ans=0,t;
     sort(judge
+1, judge+1+n);
     
while(judge[n]&&judge[n-1]&&judge[n-2])
     {
             ans
++;
             judge[n]
--;
             judge[n
-1]--;
             judge[n
-2]--;
             sort(judge
+1, judge+1+n);
     }
     
return ans;
}

int main()
{
    
int n,i;
    
while(cin>>n,n)
    {
            
int t=0 ,num; 
            
bool f=true;
            
for(i=1; i<=n; i++)
                     cin
>>color[i];
            cin
>>num;
            
for(t=0; t<=1000; t++)
            {       
                     f
=true;
                     
for(int j=1; j<=n; j++)
                            {
                                   judge[j]
=50*t;
                                   judge[j]
-=color[j];
                                   
if(judge[j]<0)f=false
                            } 
                     
if(f==true)
                     {
                        
int ans=deal(n);
                        
if( ans>=num) { cout<<t<<endl; break; }      
                     }
            }
                  
    }

    system(
"pause");
    
return 0;
}

posted on 2010-08-07 16:56 田兵 阅读(343) 评论(0)  编辑 收藏 引用 所属分类: 算法笔记


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年6月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜