P1086 peanut picking (Greed & Simulation)

2021-08-10 08:04:29

P1086 Peanut picking （ greedy & simulation ）

Subject portal

The question ： Give a matrix , According to greedy thinking, how many peanuts can you get at most and return within the specified time .

Ideas ： Because it is greedy, just sort the points with peanuts directly , Then traverse each judgment .

AC Code ：

``````#include<bits/stdc++.h>
using namespace std;
struct p{
int x,y,w;
}a[405];
int m,n,k,id=0,ans=0,te=0;//te (time)  Current time
bool cmp(p a,p b){
return a.w>b.w;
}
int main(){
cin>>m>>n>>k;
for(int i=1;i<=m;i++)
for(int j=1,tmp;j<=n;j++){
cin>>tmp;
if(tmp) a[++id].x=i,a[id].y=j,a[id].w=tmp;
}
sort(a+1,a+id+1,cmp);//Greedy
for(int i=1,tmp;i<=id;i++){
tmp=a[i].x;
if(i==1) te+=tmp+1;// Special judgement
else te+=abs(a[i].x-a[i-1].x)+abs(a[i].y-a[i-1].y)+1;
if(te+tmp<=k) ans+=a[i].w;// If you can go back
}
cout<<ans<<endl;
return 0;
}
```

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
```

https://chowdera.com/2021/08/20210810080205566L.html