一年级儿歌大雨和小雨:看看我的"NOI2004第二题,花生采摘程序."有毛病么?

来源:百度文库 编辑:高考问答 时间:2024/05/06 18:13:23
#include<stdio.h>
#include<math.h>
main()
{
FILE *pf1,*pf2;
int m,n,time;
int dat[16][16];
int peanuts=0,max,maxn,maxm;
int i,j,mn,mm,q=1,s;
pf1=fopen("d:\peanuts.in","r");
pf2=fopen("d:\peanuts.out","w");
fscanf(pf1,"%d%d%d",&m,&n,&time);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
fscanf(pf1,"%d",&dat[i][j]);
fclose(pf1);
while(time>0)
{
s=0;
{
max=0; maxn=0; maxm=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(dat[i][j]>max)
{
max=dat[i][j];
maxm=i;
maxn=j;
}
}
if(q)
{
q=0;
if(time-maxm-1>0)
time=time-maxm-1;
peanuts=peanuts+dat[maxm][maxn];
dat[maxm][maxn]=0;
mn=maxn; mm=maxm; s=1;
}
else
{
if(time-abs(maxm-mm)-abs(maxn-mn)>0)
time=time-abs(maxm-mm)-abs(maxn-mn);
peanuts=peanuts+dat[maxm][maxn];
dat[maxm][maxn]=0;
mn=maxn; mm=maxm; s=1;
}
if(!s)
break;
}
fprintf(pf2,"%d",peanuts);
fclose(pf2);
printf("He can pick %d peanuts\n",peanuts);
getch();
}
数据:
6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
问题:http://www.ynjy.cn/officeall/aosai/self_list.asp?id=4599

1你需要考虑回到路上的时间,所以你的程序有两处问题
1、if(time-abs(maxm-mm)-abs(maxn-mn)>0)
这里没有判断返回距离,应该是time-abs(maxm-mm)-abs(maxn-mn)-maxm-1>0。
2、第一步判断也有同样问题,应该是if(time-2*maxm-2>0)而且后面的几句要加else,保证如果限定时间内地一棵树也跑不到的情况能输出0而不是花生最多的树的花生数
这道题加了每次取最多花生树的花生的条件,变得没有任何难度,等于是告诉考生只能用贪心算法还定好了贪心规则并且不需要最优解……

你需要考虑回到路上的时间,所以你的程序有两处问题
1、if(time-abs(maxm-mm)-abs(maxn-mn)>0)
这里没有判断返回距离,应该是time-abs(maxm-mm)-abs(maxn-mn)-maxm-1>0。
2、第一步判断也有同样问题,应该是if(time-2*maxm-2>0)而且后面的几句要加else,保证如果限定时间内地一棵树也跑不到的情况能输出0而不是花生最多的树的花生数
这道题加了每次取最多花生树的花生的条件,变得没有任何难度,等于是告诉考生只能用贪心算法还定好了贪心规则并且不需要最优解……