首页 > 代码库 > greedy2709
greedy2709
毕竟是自己写的通过的，感觉贪心的东西都比较简单哈哈。当然看了下别人的算法，其实比自己的更加高效，看后面的对比：
给你某些颜色的颜料和灰色颜料需要的体积，其中任意三种Xml其他颜色可以合成Xml灰色颜料
每组颜料包含除灰色外的其他每种颜料50ml,问最少要几组颜料才能配出所需的颜料
暴搜，首先计算配出其他颜色颜料最少需要多少组，然后依次加1，判断是否能配出灰色
判断是否能配出灰色时，计算其他每种颜色的余量，排序，依次将最多的三种颜色减1
一开始直接减了余量第三多的数目，这种策略在碰到一些特殊数据时就失效了
例如 5 200 200 200 200 200 333
减完一次后 剩下 200 200 0 0 0 233，两种200的颜料不能配了，但是如果每次减50，结果依次为：
200 200 200 200 200 333
200 200 150 150 150 283
150 150 150 150 100 233
150 100 100 100 100 183
100 100 100 50 50 133
50 50 50 50 50 83
50 50 0 0 0 33
这种情况下可以配300ml灰色
别人的：
#include <iostream>
using namespace std;
int main()
{
int colorNum;
cin >> colorNum;
while(colorNum!=0)
{
int grayNum;
int* color=new int[colorNum];
int kitsNum;
for(int i=0;i<colorNum;i++)
cin >> color[i];
cin >> grayNum;
int max=0;
for(int i=0;i<colorNum;i++)
{
if(max < color[i])
max = color[i];
}
kitsNum = max/50+(max%50==0?0:1);
int temp=kitsNum*50;
for(int i=0;i<colorNum;i++)
color[i]=temp-color[i];
while(grayNum!=0)
{
int max1=0,max2=1,max3=2;//这里只需要求最大的三个数，而不是对整个数组进行排序，用这种方法比快速排序应该快。
for(int i=3;i<colorNum;i++)
{
if(color[i] > color[max1])
max1 = i;
else if(color[i] > color[max2])
max2 = i;
else if(color[i] > color[max3])
max3 = i;
}
if(color[max1]>0 && color[max2]!=0 && color[max3]!=0)
{
color[max1]--;
color[max2]--;
color[max3]--;
grayNum--;
}
else
{
kitsNum++;//这里并不是因为不够用又全部重新计算，而是全部加上50后，接着未完成的继续算，这里也比自己的高效。
for(int i=0;i<colorNum;i++)
color[i]+=50;
}
}
cout << kitsNum << endl;
cin >> colorNum;
}
}
自己的：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int cmpmax(int a,int b)
{
return a>b;
}
int num;
int grey,used,totalused,cur_grey;
int main()
{
int i,tempi,temp[13],s[13];
while(scanf("%d",&num),num)
{
for(i=1;i<=num;i++)
scanf("%d",&s[i]);
scanf("%d",&grey);
int max=-99;
for(i=1;i<=num;i++)
{
if(s[i]>max)
{
max=s[i];
tempi=i;
}
}
if(max%50==0)
used=max/50;
else used=max/50+1;
totalused=used*50;
for(i=1;i<=num;i++)
s[i]=totalused-s[i];
for(i=1;i<=num;i++)
temp[i]=s[i];
cur_grey=0;
if(cur_grey!=grey)
{
while(1)
{
sort(s+1,s+1+num,cmpmax);
if(s[3]==0)
{
for(i=1;i<=num;i++)
s[i]=temp[i];
cur_grey=0;
used++;
for(i=1;i<=num;i++)
{
s[i]+=50;
temp[i]=s[i];
}
}
else
{
s[1]--;
s[2]--;
s[3]--;
cur_grey++;
if(cur_grey==grey)
break;
}
}
}
printf("%d\n",used);
}
return 1;
}
greedy2709