stdKonjac's Blog

An AC a day keeps the WA away ~

【Jump】

【问题描述】

r64喜欢跳高,但是他的技术并不好,所以他想好好练习一下。

练习场上有一个个高度不一定一样的平台。最底下的是地板,高度为0。有n个平台,第i个平台的高度为hi(hi≥0)。作为一名跳高爱好者,r64希望跳到尽可能高的平台。

但是r64的技术并不好,他的最大跳跃高度是△h。也就是说,如果r64当前高度为h1,某个平台的高度为h2(h2≥h1),那么r64能跳到这个平台,当且仅当h2≤h1+△h。之后,r64的高度变成h2、

除此之外,r64规定他自己不能多次跳上同一个平台。

r64想知道,他最多能跳多高。并且,在跳的尽量高的前提下,他最多经过多少个平台,最少经过多少个平台。

【输入格式】

输入文件的第一行有两个整数n和△h,分别表示平台个数和r64的最大跳跃高度。

接下来一行有n个非负整数h1、h2、h3……hn,表示每个平台的高度。

【输出格式】

输出文件应该只包括一行三个整数maxh,maxjump,minjump,分别表示r64能跳的最大高度,他跳到高度maxh所经过的平台数量的最大值与最小值。

【输入样例】

5 2

1 2 3 5 3

【输出样例】

5 5 3

【输出样例说明】

经过平台为5的一种跳法是:0——>1>——2>——>3——>3——>5

经过平台数量为3的一种跳法是:0——>2——>3——>5当然0——>1——>3——>5也是可以的

【数据说明】

对于100%的测试数据:n≤1000000,hi≤1000000000

先O(N)扫一遍所有平台,当两个平台出现不能跳上的情况的时候,下面那个平台就是能跳的最高高度maxh,跳最多次自然是每个格子都跳,最少的话就模拟,每次选能跳的最远的那个格子跳即可。

下面是代码:

 

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.