实验1-2 爆气球

大家好，欢迎来到IT知识分享网。

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

输入格式：

输入第一行有两个正整数：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>
#include<algorithm>
using namespace std;
const int N = 1e5 + 1;
int a[N];
int main()
{

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {

        cin >> a[i];
    }
    int y = 0;
    int z = -1;
    int q = 0;
    for (int i = 0; i < n; i++) {

        y = 0;
        int t = a[i] + m;
        int start = i;
        while (start < n && a[start] <= t) {

            if (a[start] >= a[i]) {

                y++;
            }
            start++;
        }
        if (y > z) {

            z = y;
            q = start;
        }
    }
    cout << a[q-1] – m << ” ” << z << endl;
}