P1086 花生采摘 （贪心模拟）
P1086 花生采摘 （贪心&模拟）
作者：Harris-H
题目传送门
题意：给一矩阵,按贪心思路最多能才多少花生并在规定时间内返回。
思路：由于是贪心所以直接对有花生的点排序一下就好了，然后遍历每次判断一下即可。
AC代码：
#include
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>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;
}
作者：Harris-H
