P1086
HighPerformanceRobot
2018-12-09 18:14:39
## 先讲题目
这一道题的主要要注意的地方:
1.题目规定用贪心!不是求规定时间内最大采摘总数!
2.注意采摘一棵花生需要1单位时间!~~(被卡了半个小时的我笑笑)~~
这说明,看题在NOIP中非常重要。
模拟嘛,不多说了,看注释。
```cpp
#include<bits/stdc++.h> //万能头真的很好用!
using namespace std;
int nowx,nowy,nowval; //模拟的时候的坐标,最后一个么,,好吧我懒,不想开一个数组存图……
int length; //保存所有有花生的植株的个数
int m,n,k;
int ans; //答案
struct node //结构体存花生
{
int x,y,val; //坐标和花生数
} que[400];
bool cmp(node x,node y) //排序函数,花生多的排前面
{
return x.val>y.val;
}
int main()
{
ios::sync_with_stdio(0);
cin>>m>>n>>k;
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
{
cin>>nowval;
if(nowval) //不为0
{
que[length].x=i;
que[length].y=j;
que[length++].val=nowval;
}
}
sort(que,que+length,cmp);
int i=0;
nowy=que[0].y; //可以从路边最靠近第一颗花生的地方到田里去
while(k>abs(que[i].x-nowx)+abs(que[i].y-nowy)&&i<length)
{
if(k<nowx) //没时间出来了
break;
k-=(abs(que[i].x-nowx)+abs(que[i].y-nowy)+1);
nowx=que[i].x;
nowy=que[i].y;
ans+=que[i].val;
i++; //接着采花生
}
k-=nowx; //跑出来
if(k<0) //时间不够
ans-=que[i-1].val; //倒退回上一颗
cout<<ans<<endl;
return 0;
}
```