Help Jimmy

2021年09月15日 阅读数:2
这篇文章主要向大家介绍Help Jimmy,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。


#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX_N 1000
#define INFINITE 1000000
int t, n, x, y, max_h;ios

struct Platform{
     int Lx, Rx, h;
     bool operator < (const Platform& b) const
     {  
         return h > b.h;
     }   
};
//int MyCompare( const void * e1, const void * e2 )
//{
//    Platform * p1, * p2;
//    p1 = (Platform * ) e1;
//    p2 = (Platform * ) e2;
//    return p2->h - p1->h;
//}
Platform aPlatform[MAX_N + 10];
int aLeftMinTime[MAX_N + 10];
int aRightMinTime[MAX_N + 10];spa

/*
1
3 8 17 20
0 10 8
0 10 13
4 14 3orm

*/
int MinTime(int L, bool left)
{
     int y = aPlatform[L].h;
     int x;
    
     if(left)
         x=aPlatform[L].Lx;
     else
         x=aPlatform[L].Rx;
     //检查是否L底下有平台
     int j=-1;
     for(int i=L+1;i<=n;i++)
     {
         if(aPlatform[i].Lx<=x && x<=aPlatform[i].Rx )
         {
             j=i;
             break;   
         }   
     }string

    if(j==-1)//底下没平台
         if(y > max_h)
             return INFINITE;
         else
             return y;
     // 有平台的状况
     // 一、若是高度超过
     if(aPlatform[L].h - aPlatform[j].h > max_h)
         return  INFINITE;
     // 二、没超过,就计算左边的时间和右边的时间,取二者中最短的
    
    
     int hTime=aPlatform[L].h - aPlatform[j].h;//下落时间
     int leftTime=x-aPlatform[j].Lx;//向左走的时间
     int rightTime=aPlatform[j].Rx-x;//向右走的时间
     if(aLeftMinTime[j]==-1)
         aLeftMinTime[j]=MinTime(j, true);
     if(aRightMinTime[j]==-1)
         aRightMinTime[j]=MinTime(j, false);
     if(leftTime+aLeftMinTime[j]<rightTime+aRightMinTime[j])
         return hTime+leftTime+aLeftMinTime[j];//下落+向左+下层向左掉落
     else
         return hTime+rightTime+aRightMinTime[j];
}it

int main()
{
     scanf("%d", &t);
     for( int i = 0;i < t; i ++ ) {
         memset(aLeftMinTime, -1, sizeof(aLeftMinTime));
         memset(aRightMinTime, -1, sizeof(aRightMinTime));
         scanf("%d%d%d%d", &n, &x, &y, &max_h);
         aPlatform[0].Lx=aPlatform[0].Rx=x;
         aPlatform[0].h =y;
         for(int j=1;j<=n;j++)
             scanf("%d%d%d", & aPlatform[j].Lx, & aPlatform[j].Rx, & aPlatform[j].h);
         sort(aPlatform, aPlatform+n+1);
//        qsort(aPlatform, n+1, sizeof(Platform), MyCompare);
//        for(int i=0;i<=n;i++)
//        {
//            printf("%d %d %d ",  aPlatform[i].Lx,  aPlatform[i].Rx, aPlatform[i].h);
//        }
         printf("%d\n", MinTime(0, true));
     }io

    return 0;
} form



递推方式stream


#include <cstdio> im

#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_N 1000
#define INFINITE 1000000
int t, n, x, y, MAX;
struct Platform{
    int Lx, Rx, h;
    //根据h从小到大排列
    bool operator <(const Platform& r) const
    {
        return h<r.h;
    }
} ;
Platform aPlatform[MAX_N + 10];
int aLeftMinTime[MAX_N + 10];
int aRightMinTime[MAX_N + 10];

int main()
{
    scanf("%d", &t);
    for( int i = 0;i < t; i ++ ) {
        memset(aLeftMinTime, 0x3f, sizeof(aLeftMinTime));
        memset(aRightMinTime, 0x3f, sizeof(aRightMinTime));
        scanf("%d%d%d%d", &n, &x, &y, &MAX);
        aPlatform[n].Lx = x;
        aPlatform[n].Rx = x;
        aPlatform[n].h = y;
        for( int j = 0; j < n; j ++ )
            scanf("%d%d%d", & aPlatform[j].Lx, & aPlatform[j].Rx, & aPlatform[j].h);
        //qsort(aPlatform, n+1, sizeof(Platform), MyCompare);
        sort(aPlatform, aPlatform+n);
        // 最下面的平台开始,从下往上倒推
        for(int j=0;j<=n;j++)
        {
            //分别找左边和右边掉落,碰到的平台编号
            int lp=-1, rp=-1;
            for(int k=j-1;k>=0;k--)
            {
                if(lp==-1 && aPlatform[k].Lx<=aPlatform[j].Lx && aPlatform[k].Rx>=aPlatform[j].Lx)
                {
                    lp=k;
                }
                if(rp==-1 && aPlatform[k].Lx<=aPlatform[j].Rx && aPlatform[k].Rx>=aPlatform[j].Rx)
                {
                    rp=k;
                }
            }
            if(lp==-1 && aPlatform[j].h<=MAX)
                aLeftMinTime[j]=aPlatform[j].h;
            if(rp==-1 && aPlatform[j].h<=MAX)
                aRightMinTime[j]=aPlatform[j].h;
            if(lp!=-1 && (aPlatform[j].h-aPlatform[lp].h)<=MAX)
            {
                aLeftMinTime[j]=aPlatform[j].h-aPlatform[lp].h
                        + min(aPlatform[j].Lx-aPlatform[lp].Lx+aLeftMinTime[lp],aPlatform[lp].Rx-aPlatform[j].Lx+aRightMinTime[lp]);
            }
            if(rp!=-1 && (aPlatform[j].h-aPlatform[rp].h)<=MAX)
            {
                aRightMinTime[j]=aPlatform[j].h-aPlatform[rp].h
                        + min(aPlatform[j].Rx-aPlatform[rp].Lx+aLeftMinTime[rp],aPlatform[rp].Rx-aPlatform[j].Rx+aRightMinTime[rp]);
            }

        }
        printf("%d\n", aLeftMinTime[n]);
//        printf("%d\n", aRightMinTime[n]);
    }
}

/*
1
4 14 5 6
3 22 1
16 23 2
16 30 3
13 21 4

答案:15


 */