自动搬运

查看原文

来自洛谷，原作者为

	Yxa_Sheep 打表过样例，暴力出奇迹，搜索真牛逼，骗分进省一||深搜 MLE，广搜 TLE，打表 RE，退火又 CE||删掉 display 看主页||被封取关（解封后私信）||六年级蒟蒻 ，代词请用“他”||当前状态：<离线>

搬运于2025-08-24 21:18:27，当前版本为作者最后更新于2025-06-27 07:43:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

看不懂大佬写的，只好写个简简单单的桶排（话说这不是黄题吗，感觉别的题解写的至少是绿题的代码）

题意

选定一个长度为 $k$ 的区间，求 $|a_i-x|+|a_{i+1}-x|+\dots +|a_{i + k - 1}-x|$ 的最小值，$x$ 为任意自然数。

思路

$x$ 很显然得是中间数，然后遍历每个长度为 $k$ 的区间，加和就可以了，最后比大小输出。这里求中间数得排序，如果用快排时间复杂度就比较高了，$O(n \times k \times \log{k})$，会超时两个点。题目中说金箍棒的高度小于 $1000$，所以这时候就体现了桶排序的优势，时间复杂度变成了 $O(n\times k)$。细节看代码。

代码

#include <bits/stdc++.h>
using namespace std;
int n, k, cnt, x, sum, ans = INT_MAX, a[10010], b[1010];
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n - k + 1; i++)
    {
        cnt = 0, sum = 0, memset(b, 0, sizeof(b));
        for (int j = 1; j <= k; j++)
            b[a[i + j - 1]]++;
        for (int j = 1; j <= 1000; j++)
        {
            cnt += b[j];
            if (cnt >= (k - 1 >> 1) + 1)
            {
                x = j;
                break;
            }
        }
        for (int j = 1; j <= k; j++)
            sum += abs(a[i + j - 1] - x);
        ans = min(ans, sum);
    }
    printf("%d", ans);
    return 0;
}

题解来之不易，且看且珍惜。给个赞再走吧。

题目传送门