题解 P1086 【花生采摘】

众所周知,猴子只会走直线,所以......两点间的距离就是横坐标之差加上纵坐标之差

1. 众所周知,猴子的智商不如程序猿,是不会打牌的。

2. 因为一定要从最大植株摘到最小植株,所以路线是固定的

3. 简单的模拟:如果摘了花生后回不去就別摘,摘了后回得去就去摘。

#include<bits/stdc++.h>
 using namespace std;
 int m,n,t,tot,x,ti,sh;//ti:现所花时间;sh:现收获花生数量(收获的拼音“sh”) 
 struct node{
    int x,y,sl;//x:横坐标;y:纵坐标;sl:花生数量 
 }hs[405];//结构体:存放田中有花生的植株 
 bool compare(node a,node b)
 {
    return a.sl>b.sl;//结构体sort,<表示升序,>表示降序 
 }
 int main()
 {
    scanf("%d%d%d",&m,&n,&t);//注入灵魂 
    for(int i=1;i<=m;i++)
      for(int j=1;j<=n;j++)
        {
            scanf("%d",&x); //有的植株是花生植株,有的是空植株 
            if(x) hs[++tot].x=i,hs[tot].y=j,hs[tot].sl=x;//如果有花生才进行记录,避免矩阵浪费时间 
         }//tot表示花生植株数 
    sort(hs+1,hs+tot+1,compare);//花生多的放前面 
    if(hs[1].x+1>t) {cout<<0;return 0;}//如果连采最大的花生也采不到就别采了( 跳到花生要x时间,采摘1时间,跳回也要x时间) 
    else {ti=hs[1].x+1;sh=hs[1].sl;}//能就采他丫的 
    for(int i=2;i<=tot;i++)//第一株已经采了,从第二株开始采 
        if((ti+abs(hs[i].x-hs[i-1].x)+abs(hs[i].y-hs[i-1].y)+hs[i].x+1)<=t){//如果原有时间+横坐标之差+纵坐标之差+跳回路边的时间+采摘的1时间不会超过有的时间就跳过去摘 
          ti+=abs(hs[i].x-hs[i-1].x)+abs(hs[i].y-hs[i-1].y)+1;//现所花时间+=横坐标之差+纵坐标之差+采摘的1时间
          sh+=hs[i].sl;//把花生揣到怀里 
        }
        else break;//因为一定要从最多的依次到最少的,所以如果不能采就别采了,别太贪心 
    cout<<sh;//输出功力 
    return 0;
 }

 

  

上一篇:自己动手用golang实现单向链表


下一篇:MANN SL 8340