Help Jimmy

朴灿烈づ我的快乐病毒、 2022-04-13 09:28 174阅读 0赞

### Description ###

“Help Jimmy” 是在下图所示的场景上完成的游戏。  
场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。  
Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。  
设计一个程序，计算Jimmy到底地面时可能的最早时间。  
Input  
第一行是测试数据的组数t（0 <= t <= 20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N是平台的数目（不包括地面），X和Y是Jimmy开始下落的位置的横竖坐标，MAX是一次下落的最大高度。接下来的N行每行描述一个平台，包括三个整数，X1\[i\]，X2\[i\]和H\[i\]。H\[i\]表示平台的高度，X1\[i\]和X2\[i\]表示平台左右端点的横坐标。1 <= N <= 1000，-20000 <= X, X1\[i\], X2\[i\] <= 20000，0 < H\[i\] < Y <= 20000（i = 1…N）。所有坐标的单位都是米。  
Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保证问题一定有解。  
Output  
对输入的每组测试数据，输出一个整数，Jimmy到底地面时可能的最早时间。  
Sample Input  
1  
3 8 17 20  
0 10 8  
0 10 13  
4 14 3  
Sample Output  
23

##### 分析： #####

对于每一块板都有向左和向右走两种情况。因此，求出向左时和向右时两种情况的时间。然后比较，并返回其中小的一个。  
此题有点像装箱问题或是数字三角的简单变形。同样需要用一个数组来保存状态，否则会时间超限。本题本意上就是一个dp。

#include"stdio.h"
    #include"string.h"
    struct plat
    {
        long long x;
        long long y;
        long long h;
    } plth[1001],T;//这里是保存每个板块的基本信息的。
    long long N,MAX;//N个数据，MAX表示不能超过的最大高度
    long long minleft[1001];//表示第i块板往左走的最小时间。也是保存状态的
    long long minright[1001];//表示第i块板往右走的最小时间。也是保存状态的
    
    long long Mintime(long long l,long long bool1)//求最小时间函数
    {
        long long x,y,i;
        long long Minlefttime;
        long long Minrighttime;
        if(bool1==1)//bool1值为1，则表示往左走
        {
            x=plth[l].x;
        }
        else
            x=plth[l].y;
      y=plth[l].h;//高度，y表示高度
      for(i=l+1;i<=N;i++)//循环找出来，第l块板的左边/右边的下方是哪一个块板
      {
          if(x>=plth[i].x&&x<=plth[i].y)
            break;
      }
      if(i<=N)//如果是提前退出的，则表示第i块板是下方板
      {
          if(y-plth[i].h>MAX)//看两板之间的距离，是否大于max，如果不大于 则先不处理
             return 10000000;
      }
      else//如果下方没板了。
      {
          if(y>MAX)//看此板与下方的距离是否大于max，大于 则返回无穷大
            return 10000000;
          else//否则返回y值即可
            return y;
      }
      //上述操作后，，仍未执行return的。 是满足下方有板，且板与板之间的高度为超过max。
    Minlefttime=y-plth[i].h+x-plth[i].x;//将板与板之间的高度和到达下方板左边的距离相加，即是往左边走的时间，因为是1秒一米
    Minrighttime=y-plth[i].h+plth[i].y-x;//同上
    if(minleft[i]==-1)//如果==-1， 则证明之前未执行过此板，现在执行
       minleft[i]=Mintime(i,1)
    if(minright[i]==-1)
       minright[i]=Mintime(i,0);
    Minlefttime+=minleft[i];//将minleft[i]中的值表示此板往左边时最小的时间。加上到达此板的时间。即是总时间。
    Minrighttime+=minright[i];//同上
    if(Minlefttime<Minrighttime)//返回往左走和往右走的两者中小的那一个。 
        return Minlefttime;
    else
        return Minrighttime;
    
    
    }
    int main()
    {
        long long t,mintime;
        long long x,h,i,j;
        while(~scanf("%lld",&t))
        {
            while(t--)
            {   memset(minleft,-1,sizeof(minleft));
                memset(minright,-1,sizeof(minright));
                scanf("%lld%lld%lld%lld",&N,&x,&h,&MAX);
                plth[0].x=x;plth[0].y=x;plth[0].h=h;
                for(i=1;i<=N;i++)
                {
                    scanf("%lld%lld%lld",&plth[i].x,&plth[i].y,&plth[i].h);
    
                }
                for(i=0;i<N;i++)
                    for(j=i;j<=N;j++)
                {
                    if(plth[i].h<plth[j].h)
                    {
                        T=plth[i];
                        plth[i]=plth[j];
                        plth[j]=T;
                    }
                }
             mintime=Mintime(0,1);
            printf("%lld\n",mintime);
    
            }
        }
    }