首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#7560

爆气球 爆气球对孩子们来说是很好玩的游戏。假设有 n 只气球被布置在一条直线上,游戏的目标很简单,就是爆掉尽可能多的气球。但是这里我们加一条特殊的规则 —— 你…

爆气球

爆气球对孩子们来说是很好玩的游戏。假设有 n 只气球被布置在一条直线上,游戏的目标很简单,就是爆掉尽可能多的气球。但是这里我们加一条特殊的规则 —— 你只能跳一次。我们假设聪明的娃穿了件浑身带刺的衣服,跳到某个位置,躺平,这样气球只要碰到娃身体的任何部分都会立刻爆炸。那么你的任务就是告诉娃应该跳到哪里,才能一次爆掉最多的气球。

时间限制:4000

内存限制:262144

输入

输入第一行两个正整数:n(≤ 105)为一条线上布置的气球的数量;h(≤ 103)为孩子伸直双臂能达到的高度。第二行给出 n 个整数,每个对应一只气球在直线轴上的坐标。题目保证坐标按递增顺序给出,所有坐标值在 [-106, 106] 区间内。

输出

在一行中输出孩子跳跃的位置坐标,使得孩子跳到这个位置然后躺平能够爆掉身下最多的气球;随后输出能爆掉的气球的最大数量。如果这个坐标不唯一,输出最小的那个值。 一行中的数间应有 1 个空格。


样例输入

11 120
-120 -40 0 80 122 140 160 220 240 260 300

样例输出

120 5

提示

注意:跳到从 120 到140,或 240 到 260 之间的任何位置,都可以爆掉 5 只气球,所以 120 作为最小的坐标被输出。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;algorithm&gt; using namespace std; const int N = 1e5 + 1; int a[N]; int main() {     int n, m;     cin &gt;&gt; n &gt;&gt; m;     for (int i = 0; i &lt; n; i++) {         cin &gt;&gt; a[i];     }     int y = 0;     int z = -1;     int q = 0;     for (int i = 0; i &lt; n; i++) {         y = 0;         int t = a[i] + m;         int start = i;         while (start &lt; n &amp;&amp; a[start] &lt;= t) {             if (a[start] &gt;= a[i]) {                 y++;             }             start++;         }         if (y &gt; z) {             z = y;             q = start;         }     }     cout &lt;&lt; a[q-1] - m &lt;&lt; " " &lt;&lt; z &lt;&lt; endl; }</pre>
这道题暂未补解析。