当前位置:网站首页>P1086 peanut picking (Greed & Simulation)

P1086 peanut picking (Greed & Simulation)

2021-08-10 08:04:29 wx6110fa547fd20

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.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210810080205566L.html

随机推荐