這個題目是標准的貪心算法。題目的大體意思就是，現在給你一些水塘現在這個小孩在池塘1，現在開始釣魚，剛開始每個池塘有一定數目的魚，每次釣魚5分鐘魚的數目會相應的減少，當池塘當前的魚-每釣一次減少的數目<=0的時候下次將釣不到魚，當然池塘與池塘之間是有一定間隔的，這個間隔體現在時間上就是從i到i+1所花費的時間是ti當然這個ti*5才是真正的時間了。現在給你這個小孩能釣魚的時間求他最多能釣多少魚，並且要求輸出在每個池塘停留的時間。這個題目的做法就是如果我們知道了最後是在哪個池塘停止釣魚的，然後當然我們是一次走過去不會從i號池塘往回走，其余的時間全部都用來釣魚。現在的問題就是怎麼安排在這幾個池塘的釣魚時間，當然我們先是選擇出前5分鐘魚最多的池塘釣，然後這個池塘的魚減掉每次減少的魚的數目，然後下一個5分鐘繼續這種做法。要注意題目的輸出有個要求，導致必須要把最後停滯在第一個湖的這種情況單獨進行計算。還有這個題目隱含了一個意思，這些時間必須全部都耗盡，即使已經沒有魚可釣。
下面看程序。
[cpp]
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<stdio.h>
using namespace std;
int start[26],change[26],stay[26],compare[26],de[26],dis[26];
int main()
{
int n,h,i,time,sum,used,flag,maxi,j,jilu,sumc;
while(cin>>n)
{
if(n==0)
break;
cin>>h;
h=h*60;
for(i=1;i<=n;i++)
scanf("%d",&start[i]);
start[0]=0;
for(i=1;i<=n;i++)
scanf("%d",&de[i]);
for(i=1;i<n;i++)
{
scanf("%d",&dis[i]);
dis[i]=5*dis[i];
}
dis[0]=0;
for(i=1;i<=n;i++)
stay[i]=0;
sum=0;
time=h;
change[1]=start[1];
for(i=1;i<=n;i++)
stay[i]=0;
while(time>0)
{
sum=sum+change[1];
change[1]=change[1]-de[1];
if(change[1]<0)
change[1]=0;
time=time-5;
stay[1]=stay[1]+5;
}
used=0;
for(i=2;i<=n;i++)
{
sumc=0;
used=used+dis[i-1];
time=h-used;
flag=1;
for(j=1;j<=n;j++)
{
change[j]=start[j];
compare[j]=0;
}
while(time>0)
{
maxi=0;
jilu=1;
for(j=1;j<=i;j++)
{
if(change[j]>maxi)
{
maxi=change[j];
jilu=j;
}
}
sumc=sumc+maxi;
change[jilu]=change[jilu]-de[jilu];
compare[jilu]=compare[jilu]+5;
if(change[jilu]<0)
change[jilu]=0;
time=time-5;
}
if(sumc>sum)
{
sum=sumc;
for(int k=1;k<=n;k++)
stay[k]=compare[k];
}
}
for(i=1;i<n;i++)
cout<<stay[i]<<", ";
cout<<stay[n]<<endl;
cout<<"Number of fish expected: "<<sum<<endl<<endl;
}
return 0;
}
</SPAN>
#include<iostream>
#include<stdio.h>
using namespace std;
int start[26],change[26],stay[26],compare[26],de[26],dis[26];
int main()
{
int n,h,i,time,sum,used,flag,maxi,j,jilu,sumc;
while(cin>>n)
{
if(n==0)
break;
cin>>h;
h=h*60;
for(i=1;i<=n;i++)
scanf("%d",&start[i]);
start[0]=0;
for(i=1;i<=n;i++)
scanf("%d",&de[i]);
for(i=1;i<n;i++)
{
scanf("%d",&dis[i]);
dis[i]=5*dis[i];
}
dis[0]=0;
for(i=1;i<=n;i++)
stay[i]=0;
sum=0;
time=h;
change[1]=start[1];
for(i=1;i<=n;i++)
stay[i]=0;
while(time>0)
{
sum=sum+change[1];
change[1]=change[1]-de[1];
if(change[1]<0)
change[1]=0;
time=time-5;
stay[1]=stay[1]+5;
}
used=0;
for(i=2;i<=n;i++)
{
sumc=0;
used=used+dis[i-1];
time=h-used;
flag=1;
for(j=1;j<=n;j++)
{
change[j]=start[j];
compare[j]=0;
}
while(time>0)
{
maxi=0;
jilu=1;
for(j=1;j<=i;j++)
{
if(change[j]>maxi)
{
maxi=change[j];
jilu=j;
}
}
sumc=sumc+maxi;
change[jilu]=change[jilu]-de[jilu];
compare[jilu]=compare[jilu]+5;
if(change[jilu]<0)
change[jilu]=0;
time=time-5;
}
if(sumc>sum)
{
sum=sumc;
for(int k=1;k<=n;k++)
stay[k]=compare[k];
}
}
for(i=1;i<n;i++)
cout<<stay[i]<<", ";
cout<<stay[n]<<endl;
cout<<"Number of fish expected: "<<sum<<endl<<endl;
}
return 0;
}
