**这道题不是搜索题**
_**“你先找出花生最多的植株,去采摘它的花生;然后再找出剩下的植株里花生最多的,去采摘它的花生;依此类推,不过你一定要在我限定的时间内回到路边。”**_
题目中已经告诉你多多的采花生的顺序
by whr0612 @ 2022-10-24 21:27:27
用模拟+曼哈顿距离
代码如下
```cpp
#include<bits/stdc++.h>
using namespace std;
int m,n,k,ans;
struct stru{
int data,x,y;//花生的数量,坐标
}a[402];
int ai;
//比较函数
bool cmp(stru x,stru y){
return x.data>y.data;
}
int main(){
//读入
scanf("%d%d%d",&m,&n,&k);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++){
int tzy;
scanf("%d",&tzy);
if(tzy!=0){
ai++;
//保存每个有花生的植株的位置和花生的数量
a[ai].data=tzy;
a[ai].x=i;
a[ai].y=j;
}
}
//特判:没有花生
if(ai==0){
printf("0\n");
return 0;
}
sort(a+1,a+ai+1,cmp);//按花生数量排序
//枚举每株花生
//第一株特判
if(a[1].x+1>k){//如果采摘不了
printf("0\n");
return 0;
}
k-=a[1].x+1;//采摘
ans+=a[1].data;
if(a[1].x>k){//判断能不能返回
printf("0\n");
return 0;
}
for(int i=2;i<=ai;i++){
int u=a[i].x;//返回时间
if(k-(abs(a[i].x-a[i-1].x)+abs(a[i].y-a[i-1].y)+1)>=u){//如果采摘后能返回
k-=(abs(a[i].x-a[i-1].x)+abs(a[i].y-a[i-1].y)+1);//采摘
ans+=a[i].data;
}
else{//不然直接返回
printf("%d\n",ans);
return 0;
}
}
//输出答案
printf("%d\n",ans);
return 0;
}
```
by whr0612 @ 2022-10-24 22:13:47