这道题只是普通的模拟,不是贪心!
重点在于这句话:“然后再找出剩下的植株里花生最多的,去采摘它的花生”。
也就是,你下一个必须找到剩下花生最多的,而不是按照贪心思想来考虑在限定时间内的最优解
那么,应题目要求,这只是一道简单的模拟;
思路也很简单:用结构体存下每一个有价值的花生植株,其余结了0个花生的不用管,
然后用自定义cmp函数进行按价值从大到小的顺序排序,之后从最大的开始累加,一直到再加就超过时限或者全部有结果的植株都加完了为止,之后输出答案ans就可以了;
AC代码如下:
#include<bits/stdc++.h>
using namespace std;
int m,n,k,value,num=,ans=,time1=;
struct zbx{
int x,y,peanut;
}hs[];
bool cmp(zbx a,zbx b)
{
return a.peanut>b.peanut;
}
int main(){
scanf("%d%d%d",&m,&n,&k);
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
{
scanf("%d",&value);
if(value!=)
{
++num;
hs[num].peanut=value;
hs[num].x=j;hs[num].y=i;
}
}
sort(hs+,hs+num+,cmp);
for(int i=;i<=num;i++)
{
if(i==)//第一个需要特殊判断
{
time1+=hs[].y+;
if(time1+hs[].y>k)
{
printf("");return ;
}
else ans+=hs[].peanut;
}
else//其他的普遍情况
{
time1+=abs(hs[i].x-hs[i-].x)+abs(hs[i].y-hs[i-].y)+;
if(time1+hs[i].y>k)
{
printf("%d",ans);return ;//如果过了时限,不继续累加了,输出答案直接结束程序
}
else
{
ans+=hs[i].peanut;
}
}
}
printf("%d",ans);
return ;
}
完结✿✿ヽ(°▽°)ノ✿