题解：P6874 [COCI2013-2014#6] KOCKICE

spider_men · 2024-11-16 15:33:00 · 题解

动笔算算样例可得一个性质，只要确定中间位置的数是多少，其他位置就可以直接求出。

如果我们暴枚中间的数，必然超时。

于是我们需要用二分。

如果中间位置上的数是答案，那么无论什么数，操作次数一定多于他。

所以我们只要判断关系就能判断往哪边找。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
const long long MAXX = 1e14;
long long n;
long long m[N], s[N];
long long check(long long k){
    long long count = 0;
    for (long long i = 1; i <= (n >> 1) + 1; ++i) {// n >> 1相当于n / 2
        long long a = k + n / 2 + 1 - i;
        count += abs(a - m[i]) + abs(a - s[i]);
    }
    for (long long i = (n >> 1) + 2; i <= n; ++i) {
        long long b = k + i - n / 2 - 1;
        count += abs(b - m[i]) + abs(b - s[i]);
    }
    return count;
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> m[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
    }
    long long L = 0, R = MAXX;
    while (L < R) {
        long long mid = (L + R) >> 1;
        if (check(mid) < check(mid+1)) {//如果mid+1的操作次数多于mid的，答案在左边
            R = mid;
        } else {
            L = mid + 1;
        }
    }
    cout << check(L);
    return 0;
}