[ABC268E] Chinese Restaurant (Three-Star Version) 题解

思路

hzl大佬的神仙思路。

考虑菜对轮数做贡献，可以发现一定是形如 \(0,1,2,...n/2,...0,..\) 之中的一段，研究 \(0,1,2...,n/2,...,0\)，可以通过二阶差分轻松转化，如果不是从 0 开始，则加上 \(i - p_i\) 的偏移量即可，可以开三倍空间好写一点。

#include <iostream>
#define int long long
using namespace std;
const int N = 6e5 + 10;

int n, p[N], de[N], ans = 4e18;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> p[i];
    for(int i = 0, a, b, c, d, r; i < n; i ++) {
        a = 1, b = n / 2 + 1, c = (n + 1) / 2 + 1, d = n + 1;
        if(p[i] - i > 1) a += n, b += n, c += n, d += n;
        de[a + i - p[i]] ++, de[b + i - p[i]] --, de[c + i - p[i]] --, de[d + i - p[i]] ++;
    }
    for(int i = 1; i < n * 3; i ++) de[i] += de[i - 1];
    for(int i = 1; i < n * 3; i ++) de[i] += de[i - 1];
    for(int i = 0; i < n; i ++) ans = min(ans, de[i] + de[i + n] + de[i + n * 2]);
    cout << ans << '\n';
    return 0;
}