当前位置:网站首页>P1086 花生采摘 (贪心&模拟)

P1086 花生采摘 (贪心&模拟)

2021-08-10 08:02:38 wx6110fa547fd20

P1086 花生采摘 (贪心&模拟)

 题目传送门

题意:给一矩阵,按贪心思路最多能才多少花生并在规定时间内返回。

思路:由于是贪心所以直接对有花生的点排序一下就好了,然后遍历每次判断一下即可。

AC代码:

#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) 当前用时 
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;//特判 
		 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;//如果能回去 
	}
	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://blog.51cto.com/u_15326986/3328295

随机推荐