Skip to content

14125: 【原4125】是男人就跳100层

题目

题目描述

author: Lmxyy 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4125

Description

dhh的运动并不是很好(乒乓球除外),然而他被钦定参加ACM体育节篮球项目。为了能够为班争光,他决定在比赛前好好练习练习。

众所周知,篮球比赛跳高很重要。为了锻炼自己的跳高水平,dhh参加了由xyy组建的一个叫做“是男人就跳100层”的跳高魔鬼训练项目。

在项目的练习场上,xyy搭起了\(N\)个高度不一定一样的平台。第\(i\)个平台高度是\(h_i\)。

然而dhh目前的跳高水平实在是比较捉鸡的,他能够跳的最大高度为\(\Delta h\)。也就是说,如果说dhh当前所在的平台的高度为\(h_1\),某个平台的高度\(h_2(h_2 \ge h_1)\),那么dhh能够跳到这个平台上,当且仅当\(h_2 \le h_1+\Delta h\)。之后,dhh所在平台的高度就会变成\(h_2\)。一开始dhh站在地板上,地板的高度为\(0\)(高度为\(0\)的平台不是地板)。

除此以外,由于是魔鬼训练,dhh在xyy的压迫下,不能多次跳上同一个平台。不然dhh可能就会在两个高度一样的平台上来回晃荡。

dhh看到这样的训练,感到很绝望。他想问你,他最高可以跳多高。并且在保证跳得尽量高的情况下,他最多要经过几个平台,以及最少要经过几个平台

Input Format

第一行两个正整数\(N\)和\(\Delta h\),意义如题意。

接下来一行有\(N\)个非负整数\(h_1,h_2,\dots,h_N\),表示每个平台的高度。

Output Format

输出一行共三个整数\(maxh,maxjump,minjump\),分别表示dhh能跳到的最大高度、他跳到最大高度所经过平台数量的最大值和最小值。

Sample Input 1

5 2
1 2 3 5 3

Sample Output 1

5 5 3

Sample 1 Explanation

经过平台数为\(5\)的一种跳法:\(0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 3 \rightarrow 5\)。

经过平台数为\(3\)的一种跳法:\(0 \rightarrow 2 \rightarrow 3 \rightarrow 5\)。当然\(0 \rightarrow 1 \rightarrow 3 \rightarrow 5\) 也行。

Sample Input 2

9 1
1 2 3 3 6 7 8 9 10

Sample Output 2

4 4 4

Data Range

\(0 \le \Delta h \le 10^9\)

| 数据点编号 | \(N \le \) | \(h_i \le \) | | :--------------: | :----------: | :------------: | | 1 | 1 | 10 | | 2 | 2 | 20 | | 3 | 3 | 100 | | 4 | 10 | 1000 | | 5 | 100 | 1000 | | 6 | 200 | 1000 | | 7 | 500 | 1000 | | 8 | 1000 | 1000 | | 9 | 20000 | 1000 | | 10 | 50000 | 1000 | | 11 | 100000 | 1000 | | 12 | 1000000 | 10 | | 13 | 1000000 | 1000 | | 14 | 20000 | 1000000000 | | 15 | 50000 | 1000000000 | | 16 | 100000 | 1000000000 | | 17 \(\sim\) 18 | 500000 | 1000000000 | | 19 \(\sim\) 20 | 1000000 | 1000000000 |

zqy2018's solution

/*
    Warning: the second sample input is wrong!
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, delta, a[1000005];
void init(){
    n = read(), delta = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    sort(a + 1, a + n + 1);
}
void solve(){
    int ans = 0, maxi = 0;
    a[0] = 0, a[n + 1] = a[n] + delta + 1;
    for (int i = 1; i <= n + 1; ++i){
        if (a[i] > a[i - 1] + delta){
            ans = a[i - 1];
            maxi = i - 1;
            break;
        }
    }
    int mini = 0;
    for (int i = 1, lst = 0; i <= maxi; ){
        int j = i;
        while (j <= maxi && lst + delta >= a[j])
            ++j;
        lst = a[j - 1];
        i = j;
        ++mini;
    }
    printf("%d %d %d\n", ans, maxi, mini);
}
int main(){
    init();
    solve();
    return 0;
}