如果声音不记得

览遍千秋 · 2025-02-16 19:05:30 · 题解

Source and Knowledge

2025 年 2 月语言月赛，由洛谷网校提供。

考察简单数组。

文字题解

根据题目的要求，我们可以改变连续 k 场比赛的得分。

枚举这 k 场比赛的起始场次 i，那么，终止的场次是 i+k-1。下面的代码，外层循环 i 枚举起始场次，j 枚举场次。

for (int i = 1; i + k - 1 <= n; i++) {
    for (int j = i; j <= i + k - 1; j++) {
        a[j] -= 2;
    }
    // something else here
}

对于 i\sim i+k-1 范围内的每一场比赛 j，我们修改其比分，将 a[j] 减去 2。由于另外一人的得分为 99-a[j]，将 a[j] 减去 2 的同时，自然的完成了另一人得分增加 2 的过程。

随后，我们枚举全部的比赛，统计粉边铅球可以赢的比赛数目。如果粉边铅球赢的比赛数目更多，则统计一次答案。

int win = 0;
for (int j = 1; j <= n; j++) {
    if (99 - a[j] > a[j]) win++;
}
if (win > n - win) ans++;

需要注意的是，在进行下一次比分修改时，需要撤销本次修改的比分。每一次比分修改是独立的。

综上，可以得到核心代码如下。

for (int i = 1; i + k - 1 <= n; i++) {
    for (int j = i; j <= i + k - 1; j++) {
        a[j] -= 2;
    }
    int win = 0;
    for (int j = 1; j <= n; j++) {
        if (99 - a[j] > a[j]) win++;
    }
    if (win > n - win) ans++;
    for (int j = i; j <= i + k - 1; j++) {
        a[j] += 2;
    }
}