问题描述

解题思路

程序实现

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 1001;
const int INFINITE = 10000000;

int leftMinTime[MAXN];
int rightMinTime[MAXN];

struct boards
{
    int left, right;
    int height;
};
boards board[MAXN];

int N, X, Y, MAX;

bool myCompare(boards b1, boards b2)
{
    return b1.height > b2.height;
}


int main()
{
    int t;
    cin >> t;
    for(int a = 0; a < t; a++)
        {
            cin >> N >> X >> Y >> MAX;
            board[0].left = X;
            board[0].right = X;
            board[0].height = Y;
            leftMinTime[0] = INFINITE;
            rightMinTime[0] = INFINITE;
            for(int n = 1; n <= N; n++)
                {
                    cin >> board[n].left >> board[n].right >> board[n].height;
                    leftMinTime[n] = INFINITE;
                    rightMinTime[n] = INFINITE;
                }
            sort(board + 1, board + 1 + N, myCompare);
            for(int i = N; i >= 0; i--)
                {
                    for(int j = i + 1; j <= N + 1; j++)
                        {
                            if(j == N + 1)
                                {//找不到i的左端的下面那块板子
                                    if(board[i].height > MAX)
                                        leftMinTime[i] = INFINITE;
                                    else
                                        leftMinTime[i] = board[i].height;
                                }
                            else if((j < N + 1) and (board[j].left <= board[i].left) and (board[j].right >= board[i].left))
                                {//找到i的左端的下面那块板子
                                    int hl = board[i].height - board[j].height;
                                    if(hl <= MAX)
                                        leftMinTime[i] = min(leftMinTime[i], hl + min(rightMinTime[j] + board[j].right - board[i].left, leftMinTime[j] + board[i].left - board[j].left));
                                    else
                                        leftMinTime[i] = INFINITE;
                                    break;
                                }
                        }
                    for(int j = i + 1; j <= N + 1; j++)
                        {
                            if(j == N + 1)
                                {//找不到i的右端的下面那块板子
                                    if(board[i].height > MAX)
                                        rightMinTime[i] = INFINITE;
                                    else
                                        rightMinTime[i] = board[i].height;
                                }
                            else if((j < N + 1) and (board[j].right >= board[i].right) and board[j].left <= board[i].right)
                                {//找到i的右端的下面那块板子
                                    int hr = board[i].height - board[j].height;
                                    if(hr <= MAX)
                                        rightMinTime[i] = min(rightMinTime[i],
                                                              min(rightMinTime[j] + board[j].right - board[i].right,
                                                                  leftMinTime[j] + board[i].right - board[j].left) + hr);
                                    else
                                        rightMinTime[i] = INFINITE;
                                    break;
                                }

                        }
//                    cout << leftMinTime[i] << rightMinTime[i] << endl;

                }
            int minTime = min(leftMinTime[0], rightMinTime[0]);
//            cout << minTime << endl;
//            cout << INFINITE << endl;
            if(minTime >= INFINITE)
                {
                    cout << "NO!" << endl;
                }
            else
                {
                    cout << minTime << endl;
                }

        }
}

运行结果