【数据结构与算法】爆气球——定长滑动窗口

《数据结构实验指导 - C++语言版》题目集 实验1-2 爆气球

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

输入格式：

输入第一行有两个正整数：n（≤10^5）为一条线上布置的气球的数量；h（≤10^3）为孩子伸直双臂能达到的高度。第二行给出 n 个整数，每个对应一只气球在直线轴上的坐标。题目保证坐标按递增顺序给出，所有坐标值在 [−10^6,10^6] 区间内。

输出格式：

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

一行中的数字间应有 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 <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, h;
    cin >> n >> h;
    
    vector<int> coords(n);
    for (int i = 0; i < n; ++i) {
        cin >> coords[i];
    }
    
    int max_count = 0;
    int best_pos = 0;  // 初始化最佳位置
    int left = 0;
    
    // 滑动窗口
    for (int right = 0; right < n; ++right) {
        // 维护窗口[left, right]内的坐标差不超过h
        while (coords[right] - coords[left] > h) {
            left++;
        }
        
        // 计算当前窗口内的气球数量
        int current_count = right - left + 1;
        
        // 计算当前窗口的最佳发射位置：能击中所有气球的最小位置
        // 即窗口最右侧气球的位置减去h
        int current_pos = coords[right] - h;
        
        // 更新最大数量和最佳位置
        if (current_count > max_count || 
            (current_count == max_count && current_pos < best_pos)) {
            max_count = current_count;
            best_pos = current_pos;
        }
    }
    
    cout << best_pos << " " << max_count << endl;
    
    return 0;
}