©著作权归作者所有：来自51CTO博客作者Herio的原创作品，请联系作者获取转载授权，否则将追究法律责任
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);//Greedyfor(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. 赞 收藏 评论 举报
相关文章
