[ABC268E] Chinese Restaurant (Three-Star Version) Solution

• [ABC268E] Chinese Restaurant (Three-Star Version) Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

$ n $ 个人进行圆排列，即围坐在圆桌周围，位置编号依次为 $ [0, n - 1] $，给定序列 $ P_n $ 表示第 $ i $ 个人喜欢的菜品在 $ P_i $ 处，$ P_i \in [0, n - 1] $ 且各不相同。定义每个人的沮丧值为其位置与 $ P_i $ 的距离。你可以任意旋转圆桌，以最小化所有人的沮丧值之和，求最小值。

Solution

可以说是一道思路较为简单但细节巨多，非常难调的题，到处各种加加减减与分类讨论，这么一道水题最后我写了一个半点。

首先我们可以想到，我们认为初始状态为 $ i $ 在 $ i - 1 $，然后认为初始状态之后转的格数为 $ x $ 轴，对于一个特定的人的沮丧值为 $ y $ 轴，不难想到图像应为至多三段斜率为 $ 1 $ 或 $ -1 $ 的线段组成，同时若点数为奇数，那么在距离 $ P_i $ $ \lfloor \dfrac{n}{2} \rfloor $ 和 $ \lceil \dfrac{n}{2} \rceil $ 的对应位置的值是相同的，也就是此时斜率应为 $ 0 $，但有且仅有这么一段。对于答案我们只需要将每个人的情况都合并起来求一下最小值即可，考虑如何维护。

于是我们直接考虑 $ y $ 轴的值，对于一个人的变化量显然是类似 $ -1, -1, -1, 1, 1, 1, 0, 1, \cdots $ 等，这个东西等于是做了个差分。不难发现这东西如果用线段树维护区间修改，那么最终复杂度应为 $ O(n \log n) $ 的，不过我不想写线段树，于是考虑另一种写法，不难发现这东西是很多个区间修改，所以可以对差分数组再次做差分，即二阶差分，此时我们只需要在转折点处做一下修改即可，这样最后做两次前缀和求个最大值即可。

不难发现这东西思路显然看起来很简单，但是当实现的时候就会发现阴间的地方在哪了。首先我们发现有四种情况，即 $ i $ 与 $ p_i $ 的偏序关系，和 $ (i - p_i) \bmod{n} $ 与 $ (p_i - i) \bmod{n} $ 的偏序关系。但是经过讨论我们会发现，前者的偏序关系是无意义的，因为我们求距离时可以直接转正，即 $ dis = (i - p_i + n) \bmod{n} $，所以此时优化情况为两种。

具体情况可以自己画一下然后看看代码，还是比较显然的，只是细节太多了。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template < typename T = int >
inline T read(void);

int N;
int P[210000];
ll d[210000];
ll ans(LONG_LONG_MAX);

int main(){
    N = read();
    for(int i = 0; i <= N - 1; ++i)P[i] = read();
    for(int i = 0; i <= N - 1; ++i)d[0] += min((i - P[i] + N) % N, (P[i] - i + N) % N);
    d[1] = -d[0];
    for(int i = 0; i <= N - 1; ++i)
        if((P[i] - i + N) % N <= (i - P[i] + N) % N){
            int dis = (P[i] - i + N) % N;
            d[1]--, d[dis + 1]++;
            d[dis + 1]++, d[dis + (N >> 1) + 1]--;
            d[dis + (N >> 1) + 1 + (N & 1 ? 1 : 0)]--;
        }else{
            int dis = (i - P[i] + N) % N;
            d[1]++, d[(N >> 1) - dis + 1]--;
            d[(N >> 1) - dis + 1 + (N & 1 ? 1 : 0)]--;
            d[N - dis + 1]++, d[N - dis + 1]++;
        }
    for(int i = 1; i <= N - 1; ++i)d[i] = d[i - 1] + d[i];
    for(int i = 1; i <= N - 1; ++i)d[i] = d[i - 1] + d[i];
    for(int i = 0; i <= N - 1; ++i)ans = min(ans, d[i]);
    printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2023_01_18 初稿