贪心算法,使用STL的priority_queue来维护一个队列。保证鱼数最多(相同鱼则保存标号较小的)的一个序列。然后贪心就可以了。一下是代码
#include<iostream>
#include<queue>
using namespace std;
int n,h;
int f[30],t[30],d[30];
int best[30],way[30],maxinum,tot,tag=0;
struct node
{
int num;
int fish;
void set(int id,int f)
{
num=id;
fish=f;
}
};
bool operator<(const node a,const node b)
{
if(a.fish==b.fish)
return a.num>b.num;
else
return a.fish<b.fish;
}
priority_queue<node> qu;
node now;
int main()
{
while(scanf("%d",&n)&&n)
{
if(tag)
printf("\n");
cin>>h;
h*=12;
maxinum=-1;
int i,j;
for(i=0;i<n;i++)
{
cin>>f[i];
}
for(i=0;i<n;i++)
{
cin>>d[i];
}
for(i=0;i<n-1;i++)
{
cin>>t[i];
}
///////////数据输入完毕,开始进入计算
for(i=0;i<n;i++)
{
memset(way,0,sizeof(way));
while(!qu.empty())
qu.pop();
if(i>0)
h-=t[i-1];
tot=0;
for(j=0;j<=i;j++)
{
now.set(j,f[j]);
qu.push(now);
}
for(j=0;j<h;j++)
{
now=qu.top();
qu.pop();
tot+=now.fish;
now.fish-=d[now.num];
if(now.fish<0)
now.fish=0;
way[now.num]+=5;
qu.push(now);
}
if(tot>maxinum)
{
maxinum=tot;
memcpy(best,way,sizeof(way));
}
}
printf("%d",best[0]);
for(i=1;i<n;i++)
printf(", %d",best[i]);
printf("\nNumber of fish expected: %d\n",maxinum);
tag=1;
}
return 0;
}
posted on 2010-08-21 15:09
崔佳星 阅读(1465)
评论(1) 编辑 收藏 引用 所属分类:
POJ