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

更好的阅读体验戳此进入

题面

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

Solution

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

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

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

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

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

Code

xxxxxxxxxx
69
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

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

11
using namespace std;
12

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

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

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

25
int N;
26
int P[210000];
27
ll d[210000];
28
ll ans(LONG_LONG_MAX);
29

30
int main(){
31
    N = read();
32
    for(int i = 0; i <= N - 1; ++i)P[i] = read();
33
    for(int i = 0; i <= N - 1; ++i)d[0] += min((i - P[i] + N) % N, (P[i] - i + N) % N);
34
    d[1] = -d[0];
35
    for(int i = 0; i <= N - 1; ++i)
36
        if((P[i] - i + N) % N <= (i - P[i] + N) % N){
37
            int dis = (P[i] - i + N) % N;
38
            d[1]--, d[dis + 1]++;
39
            d[dis + 1]++, d[dis + (N >> 1) + 1]--;
40
            d[dis + (N >> 1) + 1 + (N & 1 ? 1 : 0)]--;
41
        }else{
42
            int dis = (i - P[i] + N) % N;
43
            d[1]++, d[(N >> 1) - dis + 1]--;
44
            d[(N >> 1) - dis + 1 + (N & 1 ? 1 : 0)]--;
45
            d[N - dis + 1]++, d[N - dis + 1]++;
46
        }
47
    for(int i = 1; i <= N - 1; ++i)d[i] = d[i - 1] + d[i];
48
    for(int i = 1; i <= N - 1; ++i)d[i] = d[i - 1] + d[i];
49
    for(int i = 0; i <= N - 1; ++i)ans = min(ans, d[i]);
50
    printf("%lld\n", ans);
51
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
52
    return 0;
53
}
54

55
template < typename T >
56
inline T read(void){
57
    T ret(0);
58
    int flag(1);
59
    char c = getchar();
60
    while(c != '-' && !isdigit(c))c = getchar();
61
    if(c == '-')flag = -1, c = getchar();
62
    while(isdigit(c)){
63
        ret *= 10;
64
        ret += int(c - '0');
65
        c = getchar();
66
    }
67
    ret *= flag;
68
    return ret;
69
}

UPD

update-2023_01_18 初稿