题解：P16773 [GKS 2020 #G] Combination Lock

koukou · 2026-07-21 15:59:46 · 题解

一个环不好做，经典的，排序之后赋值一份破环成链。

枚举新树组中每一个长度为 W 的窗口，贪心的，最后的那个值肯定是当前窗口内的中间值。

因为排序过了，所以显然中间值左边的都小于它，右边的都大于它。于是操作次数很容易算，左边的是 a_{mid}-a_i，右边的是 a_i-a_{mid}，用前缀和加速一下即可。

:::success[代码]{open}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int T, w, n;
ll a[N], pre[N];
ll sum(int l, int r) 
{ 
    return pre[r] - pre[l - 1]; 
}
void solve(int id)
{
    cin >> w >> n;
    for(int i = 1; i <= w; i++) cin >> a[i];
    sort(a + 1, a + w + 1);
    for(int i = 1; i <= w; i++) a[i + w] = a[i] + n;
    for(int i = 1; i <= 2 * w; i++) pre[i] = pre[i - 1] + a[i];
    ll ans = 1e18;
    for(int i = 1; i <= w; i++)
    {
        int l = i, r = i + w - 1, mid = (l + r) / 2;
        ans = min(ans, a[mid] * (mid - l + 1) - sum(l, mid) + sum(mid + 1, r) - a[mid] * (r - mid));
    }
    cout << "Case #" << id << ": " << ans << "\n";
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    cin >> T;
    for(int id = 1; id <= T; id++) solve(id);
    return 0;
}

:::