问题描述

在2025年"铅球杯"决赛中，共有$n$场比赛，保证$n$为奇数。每场比赛的比分为$a_i$（红边铅球得分）和$99-a_i$（粉边铅球得分）。粉边铅球获胜的条件是$99-a_i > a_i$，即$a_i \leq 49$。

裁判蓝边铅球可以选择一个起始位置$l$（$1 \leq l \leq n-k+1$），并对从$l$开始的连续$k$场比赛进行调整：每场红边铅球扣2分，粉边铅球加2分。调整后，粉边铅球获胜的条件变为$101-a_i > a_i-2$，即$a_i \leq 51$。

粉边铅球要赢得整个决赛，需要至少获胜$\frac{n+1}{2}$场。问有多少种选择$l$的方法，使得调整后粉边铅球获胜。

算法思路

预处理与初始统计

遍历每场比赛的比分$a_i$，统计当前粉边铅球已经获胜的场数（即$a_i \leq 49$的场数），记为$\text{win}$。 对于未获胜的场次，如果$a_i$满足$50 \leq a_i \leq 51$，则这些场次经过调整后粉边铅球可以获胜。将这些场次标记在数组$b$中（$b[i] = 1$）。

需求计算

计算粉边铅球还需要获胜的场数：$\text{req} = \frac{n+1}{2} - \text{win}$。 如果$\text{req} \leq 0$，说明粉边铅球已经获胜，任何起始位置$l$都满足条件，输出$n$。 如果$\text{req} > k$，说明即使调整所有$k$场比赛也无法满足需求，输出$0$。

滑动窗口检查

使用滑动窗口技术检查所有长度为$k$的连续子数组（对应起始位置$l$），统计每个子数组中$b[i] = 1$的个数（即可以通过调整获胜的场数）。 如果某个子数组中$b[i] = 1$的个数$\geq \text{req}$，则该起始位置$l$有效。

代码实现

#include<iostream>
#include<vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k, win = 0; // win记录粉边铅球当前获胜场数
    cin >> n >> k;
    int need = (n + 1) / 2; // 所需获胜场数
    vector<int> a(n + 1), b(n + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] <= 49) {
            win++; // 粉边铅球已经获胜
        } else if (a[i] <= 51) {
            b[i] = 1; // 该场次调整后粉边铅球可以获胜
        }
    }
    
    int req = need - win; // 还需要获胜的场数
    if (req <= 0) {
        cout << n << '\n'; // 所有起始位置 l 都有效
        return 0;
    }
    if (req > k) {
        cout << 0 << '\n'; // 无法通过调整满足需求
        return 0;
    }
    
    int cur = 0, ans = 0;
    // 初始化第一个窗口 [1, k]
    for (int i = 1; i <= k; i++) {
        cur += b[i];
    }
    if (cur >= req) {
        ans++;
    }
    // 滑动窗口检查所有可能的 l
    for (int i = 2; i <= n - k + 1; i++) {
        cur -= b[i - 1];
        cur += b[i + k - 1];
        if (cur >= req) {
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}