首页 > 试题广场 >

是男人就下100层

[编程题]是男人就下100层

热度指数：441 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

相信大家都听说过“是男人就下100层”系列游戏，游戏中包括多个长度和高度各不相同的平台，地面是最低的平台，高度为零，长度无限。
一个男人在开始的时候从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当他落到某个平台上时，游戏者选择让他向左或向右跑，跑动的速度也是1米/秒。当他跑到平台的边缘时会继续下落。要求每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。
请帮忙设计一个程序，计算最快到达地面所用的时间。

输入描述:

输入包含多组数据。

每组测试数据的第一行是四个整数N、X、Y、MAX，用空格分隔。N是平台的数目（不包括地面），X和Y是游戏开始时男人所在位置的坐标，MAX是一次下落的最大高度。

紧接着有N行，每行描述一个平台的信息，包括三个整数，X1[i]，X2[i]和H[i]。H[i]表示平台的高度，X1[i]和X2[i]表示平台左右端点的横坐标。

1 ≤ N ≤ 1000；-20000 ≤ X, X1[i], X2[i] ≤ 20000；1 ≤ H[i] < Y ≤ 20000（1≤i≤N）。所有坐标的单位都是米。

平台的厚度忽略不计，如果恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保证问题一定有解。

输出描述:

对应每一组输入，输出一个整数，为到达地面最早的时间。

示例1

输入

输出

算法知识视频讲解

TonyLuis

import java.util.*;

public class Main {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			Integer[][] floors = new Integer[in.nextInt()][3];
			int X = in.nextInt(), Y = in.nextInt(), MAX = in.nextInt();
			int left = Integer.MAX_VALUE, right = Integer.MIN_VALUE;
			for (int i = 0; i < floors.length; i++) {
				int temp = in.nextInt();
				left = Math.min(left, temp);
				floors[i][0] = temp;
				temp = in.nextInt();
				right = Math.max(right, temp);
				floors[i][1] = temp;
				floors[i][2] = in.nextInt();
			}
			System.out.println(calc(floors, X, Y, MAX, left, right));
		}
	}

	static int calc(Integer[][] floors, int X, int Y, int MAX, int left, int right) {
		// 横坐标对齐
		for (int i = 0; i < floors.length; i++) {
			floors[i][0] -= left;
			floors[i][1] -= left;
		}
		X -= left;
		right -= left;
		left = 0;

		// 将平台按高度排序，同高度则按横坐标排序
		Arrays.sort(floors, new Comparator<Integer[]>() {
			@Override
			public int compare(Integer[] arg0, Integer[] arg1) {
				if (arg0[2].equals(arg1[2]))
					return arg0[0] - arg1[0];
				return arg0[2] - arg1[2];
			}
		});

		// 如果X不在平台横纵坐标范围，直接掉下来即可（不考虑无解及非法情况）
		if (X < 0 || X > right || Y < floors[0][2])
			return Y;

		// dp求解,第一个值表示到达地面最小时间，第二个值表示当前往下跳的高度
		int[][] dp = new int[right + 1][2];
		int low = 0, high = floors[0][2];
		for (Integer[] floor : floors) {

			// 判断进入新的一层
			if (high < floor[2]) {
				// 上一层右边空档区
				int det = high - low;
				for (int i = left; i <= right; i++) {
					dp[i][0] += det;
					dp[i][1] += det;
				}
				// 平台高于Y值，舍弃（测试用例中貌似没有用到）
				if (high > Y) {
					high = low;
					break;
				}
				// low、high上升一层
				low = high;
				high = floor[2];
				left = 0;
			}
			int det = high - low;
			// 左边空挡区
			for (int i = left; i < floor[0]; i++) {
				dp[i][0] += det;
				dp[i][1] += det;
			}
			// 中间平台区，判断从左边、右边能否走通
			boolean isLeft = dp[floor[0]][1] + det <= MAX;
			boolean isRight = dp[floor[1]][1] + det <= MAX;
			for (int i = floor[0]; i <= floor[1]; i++) {
				if (!isLeft && !isRight) {
					dp[i][1] = MAX + 1;
					continue;
				}
				int goRight = floor[1] - i + dp[floor[1]][0] + det;
				// left取的是新值，只有最左边的需要+det
				int goLeft = i - floor[0] + dp[floor[0]][0];
				if (i == floor[0])
					goLeft += det;
				if (!isLeft)
					dp[i][0] = goRight;
				else if (!isRight)
					dp[i][0] = goLeft;
				else
					dp[i][0] = Math.min(goLeft, goRight);
				dp[i][1] = 0;
			}
			// left指针右移
			left = floor[1] + 1;
		}
		return dp[X][0] + Y - high;
	}

}

动态规划即可，注释非常详细了。

编辑于 2016-09-03 17:01:35 回复(0)

revivedSuN

将起点看作是宽度为1的一层，这样和其它层统一处理。

而从任意一层(由下向上倒数第二层以上的任意层)到最底层的最小距离为。

1.直接从起点跳到最底层。

2.从起点，跳到下一层，然后从左边缘走到最底层。

3.从起点，跳到下一层，然后从右边缘走到最底层。

上述三种情况的最小距离，即为从某层到地面时的最小距离。

初始化第一层下落的最小距离，然后递推，一直到起跳点可得答案。

发表于 2016-03-06 15:26:41 回复(0)

C/C++

Cavs

由于下落的高度和时间是一定的，我们只考虑在平台上左右移动的时间。 将平台按高度从高到低排序，这样我们遍历时只需查找比当前平台高且高度差不超
过最大下落距离的平台。 leftDp[i],rightDp[i]分别表示到平台i的左端和右端花费的最小平移时间。
leftDown[i],rightDown[i]分别表示当前平台是否能再落在未遍历的平台上。 先找出男人先落在那个平台上； 如果直接落在地上，返回男人的高度。 在高度差合适的平台内，如果上层平台左端点在该平台范围内，则更新该平台的左右端最小时间，
并把上层平台的左端标志为不可下落；同理右端点。
最后计算能落到地面的所有平台最小的平移值，再加上下落的时间即为结果。 #include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>

#define INF 1000000
using namespace std;

struct Terrace
{
	int left, right;
	int height;
};
int main(int argc, char** argv)
{
	//freopen("in.txt", "r", stdin);
	int n, x, y, maxHeight;
	while (cin >> n >> x >> y >> maxHeight)
	{
		vector<Terrace> games(n);
		for (int i = 0; i < n; ++i)
			cin >> games[i].left >> games[i].right >> games[i].height;

		sort(games.begin(), games.end(),
			[](const Terrace& t1, const Terrace& t2)
			{
				return t1.height > t2.height;
			});
		vector<int> leftDp(n, INF), rightDp(n, INF);
		bool toLand = true;
		for (int i = 0; i < n && y - games[i].height <= maxHeight; ++i)
		{
			if (games[i].left <= x && x <= games[i].right)
			{
				leftDp[i] = x - games[i].left;
				rightDp[i] = games[i].right - x;
				toLand = false;
				break;
			}
		}
		if (toLand)
		{
			cout << y << endl;
			continue;
		}

		vector<bool> leftDown(n, true), rightDown(n, true);
		for (int i = 1; i < n; ++i)
		{
			int left = games[i].left, right = games[i].right, height = games[i].height;
			for (int j = i - 1; j >= 0 && games[j].height - height <= maxHeight; --j)
			{
				if (leftDown[j] && left <= games[j].left && games[j].left <= right)
				{
					leftDown[j] = false;
					leftDp[i] = min(leftDp[i], leftDp[j] + games[j].left - left);
					rightDp[i] = min(rightDp[i], leftDp[j] + right - games[j].left);
				}
				if (rightDown[j] && left <= games[j].right && games[j].right <= right)
				{
					rightDown[j] = false;
					leftDp[i] = min(leftDp[i], rightDp[j] + games[j].right - left);
					rightDp[i] = min(rightDp[i], rightDp[j] + right - games[j].right);
				}
			}
		}

		int minTime = INF;
		for (int j = n - 1; j >= 0 && games[j].height <= maxHeight; --j)
		{
			if (leftDown[j]) minTime = min(minTime, leftDp[j]);
			if (rightDown[j]) minTime = min(minTime, rightDp[j]);
		}

		cout << minTime + y << endl;
	}

	return 0;
}

发表于 2017-07-11 20:41:09 回复(0)

C/C++

1hani1

审题出问题了，搞了半天测试发现有答案无解，才发现恰巧落在平台边上被视为落在平台上。吐槽一下这个题只能看见测试用例的最后一行，出错根本不知道错在哪

思路：由于下落高度一定，可以不考虑，只考虑横向移动。

从一个板上只能两种选择，左或者右，建立数组dp[n][2]，dp[i][0], dp[i][1]分别表示从第i个板的两边下落的最小距离。假设从左边落下之后的踩到的板子为j

那么dp[i][0] = min ( dp[j][0] +i_left - j_left, dp[j][1] + j_right-i_left)

往左往右

dp[i][1]也同理

建一个结构体，并按照高度排序，从上往下依次找落点

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct pos{
    int left;
    int right;
    int h;
    pos()=default;
    pos(int l,int r,int hh):left(l),right(r),h(hh){};
};

int main()
{
    int N,X,Y,MAX;
    while(cin>>N>>X>>Y>>MAX)
    {
       vector<pos> v(N);
       for(int i=0;i<N;i++)
       cin>>v[i].left>>v[i].right>>v[i].h;
       v.push_back(pos(-20001,20001,0)); //加入地面
       v.push_back(pos(X,X,Y));//加入目标点都是为了方便
       sort(v.begin(),v.end(),//按照高度排序
            [](const pos& one,const pos& two){return one.h<two.h;} );
       //这里注意加入了两个点，应为N+2，这里想用INT_MAX的，但是#include<limits>之后INT_MAX还是报错
       vector<vector<int>> dp(N+2,vector<int>(2,1000000));
       dp[0][0]=dp[0][1]=0;
       for(int i=1;i<=N+1;i++)
      {
         bool l=1,r=1;// 设定l和r表示是否已经处理过，毕竟不能穿过板子落到下一层
         for(int j=i-1; j>=0  && v[i].h -v[j].h <= MAX && (l||r); j--) //从高往低找
        {
            //判断左边是否能落在j板上,出错就出这里了，没加等号导致有无解的情况
           if(l && v[i].left >= v[j].left && v[i].left <= v[j].right)
          { 
            dp[i][0] = j==0 ? 0 : //如果 j板是地面，直接赋0
                 min( v[i].left - v[j].left + dp[j][0], v[j].right - v[i].left + dp[j][1]);
            l=0;
          }
           if(r && v[i].right >= v[j].left && v[i].right <= v[j].right)//判断右边是否能落在j板上
          { 
            dp[i][1] = j==0 ? 0 :
                min( v[i].right - v[j].left + dp[j][0], v[j].right - v[i].right + dp[j][1]);
            r=0;
          }
        }
      }
        cout<<Y+dp[N+1][0]<<endl; //输出高度加平移
    }
return 0;
}

编辑于 2018-07-11 16:37:11 回复(0)

hofighter

答案错误:您提交的程序没有通过所有的测试用例 测试用例: 1 0 10 100 -3 3 4 对应输出应该为: 13 你的输出为: 10

我的程序测试这个用例输出明明就是13，它提示我输出的是10。。。
牛客怎么了，感觉做了好多题答案都是对的，它给我说测试用例不对，牛客的oj系统需要改进啊！！！
思路就是用dp，好麻烦，不想说了，期待大神更新更好的方法。 #include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 20001;
const int maxk = 1001;
struct NODE{
    int x1;
    int x2;
    int h;
};

bool cmp(NODE a,NODE b){
    if(a.h!=b.h)
        return a.h>b.h;
    else
        return a.x1>b.x1;
}

int main()
{
    int n,x,y,MAX;
    int i,j;
    while(cin >> n >> x >> y >> MAX){
        struct NODE step[n+1];
        for(i=1;i<n+1;i++){
            cin >> step[i].x1 >> step[i].x2 >> step[i].h;
        }
        sort(step+1,step+n+1,cmp);
        step[0].x1 = x;
        step[0].x2 = x;
        step[0].h = y;

        int dp[n+1][2];

        for(i=0;i<=n+1;i++)
            for(j=0;j<2;j++)
                dp[i][j] = maxn;
        dp[0][0] = dp[0][1] = 0;

        for(i=1;i<=n+1;i++){
            int maxx1 = step[i-1].x1;
            int maxx2 = step[i-1].x2;
            int left;
            int right;
            for(j=1;abs(step[i-j].h-step[i].h)<=MAX && j<=i;j++){
                if(step[i-j].x1>maxx1 && step[i-j].x1 < maxx2 && step[i].x1>maxx1 && step[i].x1<maxx2){
                    left = dp[i-j][0] + min((abs(step[i-j].x1-maxx1) + abs(step[i].x1-maxx1)),(abs(step[i-j].x1-maxx2) + abs(step[i].x1-maxx2)));
                }
                else{
                    left = dp[i-j][0] + abs(step[i].x1-step[i-j].x1);
                }

                if(step[i-j].x2>maxx1 && step[i-j].x2 < maxx2 && step[i].x1>maxx1 && step[i].x1<maxx2){
                    right = dp[i-j][1] + min((abs(step[i-j].x2-maxx1) + abs(step[i].x1-maxx1)),(abs(step[i-j].x2-maxx2) + abs(step[i].x1-maxx2)));
                }
                else{
                    right = dp[i-j][1] + abs(step[i].x1-step[i-j].x2);
                }

                dp[i][0] = min(dp[i][0],min(left,right) + abs(step[i].h - step[i-j].h));

                if(step[i-j].x1>maxx1 && step[i-j].x1 < maxx2 && step[i].x2>maxx1 && step[i].x2<maxx2){
                    left = dp[i-j][0] + min((abs(step[i-j].x1-maxx1) + abs(step[i].x2-maxx1)),(abs(step[i-j].x1-maxx2) + abs(step[i].x2-maxx2)));
                }
                else{
                    left = dp[i-j][0] + abs(step[i].x2-step[i-j].x1);
                }

                if(step[i-j].x2>maxx1 && step[i-j].x2 < maxx2 && step[i].x2>maxx1 && step[i].x2<maxx2){
                    right = dp[i-j][1] + min((abs(step[i-j].x2-maxx1) + abs(step[i].x2-maxx1)),(abs(step[i-j].x2-maxx2) + abs(step[i].x2-maxx2)));
                }
                else{
                    right = dp[i-j][1] + abs(step[i].x2-step[i-j].x2);
                }

                dp[i][1] = min(dp[i][1],min(left,right) + abs(step[i].h - step[i-j].h));

                if(maxx1>min(step[i-j].x1,step[i].x1))
                    maxx1 = min(step[i-j].x1,step[i].x1);
                if(maxx2 < max(step[i-j].x2,step[i].x2))
                    maxx2 = max(step[i-j].x2,step[i].x2);
            }
        }
        int res = maxn;
        int ml = step[n].x1;
        int mr = step[n].x2;
        for(i=n;step[n].h <= MAX && i>=0;i--){
            int tmpl = maxn;
            int tmpr = maxn;
            if(step[i].x1 <= ml || step[i].x1 >= mr)
                tmpl = dp[i][0] + step[i].h;
            if(step[i].x2 <= ml || step[i].x2 >= mr)
                tmpr = dp[i][1] + step[i].h;
           // cout << step[i].x1 << " " << step[i].x2 << " ** " <<dp[i][0] << " " << dp[i][1] << " " << tmpl << " " << tmpr << endl;
            int tmp = min(tmpl,tmpr);
            res = min(res,tmp);
        }
        cout << res << endl;
    }
    return 0;
}