题解：B4298 [蓝桥杯青少年组国赛 2022] 金箍棒

Yivan11 · 2025-07-07 11:34:51 · 题解

题目传送门

前言

我们有 n 根高度各不相同的金箍棒排成一排，每次施法可以将一根金箍棒的高度增加或减少 1。现在需要选择 k 根相邻的金箍棒，通过最少的施法次数将它们的高度变为相同。求这个最少施法次数。

思路

这道题目要求我们找到 k 根相邻的金箍棒，通过最少的施法次数将它们的高度变为相同。核心思路是：首先利用滑动窗口遍历所有可能的 k 根相邻金箍棒组合，对于每个窗口，使用桶排序统计高度分布，因高度不超过 1000，快速找到使施法次数最少的中位数高度，然后计算将所有金箍棒调整到该高度所需的施法次数总和。通过维护滑动窗口内的桶排序统计信息，我们避免了重复计算，将时间复杂度优化到 O(n\times k)，能够高效处理题目给定的数据规模。最后在所有窗口结果中取最小值即为答案。

代码

#include <bits/stdc++.h>
using namespace std;
int IO(int N, int K, vector<int>& h) {
    const int ah = 1000;
    vector<int> c(ah + 1, 0);
    int io = INT_MAX;
    for (int i = 0; i < K; ++i) {
        c[h[i]]++;
    }

    for (int i = 0; i <= N - K; ++i) {
        int e = 0;
        int sum = 0;
        for (int h = 1; h <= ah; ++h) {
            sum += c[h];
            if (sum >= (K + 1) / 2) {
                e = h;
                break;
            }
        }
        int ops = 0;
        for (int h = 1; h <= ah; ++h) {
            ops += abs(h - e) * c[h];
        }
        io = min(io, ops);
        if (i + K < N) {
            c[h[i]]--;
            c[h[i + K]]++;
        }
    }

    return io;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    vector<int> h(N);
    for (int i = 0; i < N; ++i) {
        cin >> h[i];
    }
    cout << IO(N, K, h) << endl;
    return 0;
}