A30954. 爆气球爆气球对孩子们来说是很好玩的游戏。假设有 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 作为最小的坐标被输出。
参考答案
#include<iostream>
using namespace std;
int main(){
int n,h,p[100005];
cin>>n>>h;
for(int i=0;i<n;i++)
cin>>p[i];
int _max=-1,start;
for(int i=n-1;i>=0;i--){ //枚举终点 p[i]
int k=p[i]-h,s=0; //k开始位置
for(int j=i;j>=0;j--){ //找能爆掉气球的个数
if(p[j]>=k) s++;
else break; //后面的气球都达不到
}
if( s>=_max ) { //找到新的最大值
_max=s;
start = k;
}
}
cout<<start<<' '<<_max;
return 0;
}
上一题
下一题