牛客 contest 9934J Pass Through With One Breath

题目描述

Solution

我们枚举起点，然后考虑如果将第一位变成 $v$，那么第 $k$ 位是 $v+k-1$

那么总的花费就是 $\sum_{i=1}^n |v+i-1-a_i|$

令 $b_i$ 为 $a_i-i+1$，总花费变为 $\sum_{i=1}^n|v-b_i|$

显然 $v$ 取 $b$ 的中位数最优，求中位数可以用 $nth_element$ 可以做到 $O(n^2)$

#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 4010
#define ll long long
#define INF 1000000000000ll
using namespace std;

int n, a[maxn];

ll b[maxn];
void work() {
    cin >> n; 
    for (int i = 1; i <= n; ++i) cin >> a[i], a[i + n] = a[i];
    ll ans = INF;
    for (int k = 1; k <= n; ++k) {
        ll sum = 0; 
        for (int i = 1; i <= n; ++i) b[i] = a[i + k - 1] - i + 1;
        nth_element(b + 1, b + (n + 1 >> 1), b + n + 1);
        int v = b[n + 1 >> 1];
        for (int i = 1; i <= n; ++i) sum += abs(b[i] - v); 
        ans = min(ans, sum); 
    }
    cout << ans << "\n"; 
} 

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

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}