题目描述

佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有个同学，编号从到。一开始，同学们按照的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。

佳佳可向同学们下达命令，每一个命令的形式如下：

这里的值是由佳佳决定的，每次命令的值都可以不同。这个命令的作用是移动编号是的这个同学的位置。要求换到的位置上，换到的位置上，……，要求换到的位置上。执行每个命令都需要一些代价。我们假定如果一个命令要移动个人的位置，那么这个命令的代价就是。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？

输入输出格式

输入格式：

第一行是一个整数，表示一共有个同学。

其后行每行包括个不同的正整数，以一个空格隔开，分别表示编号是的同学最希望相邻的两个同学的编号，编号是的同学最希望相邻的两个同学的编号，……，编号是的同学最希望相邻的两个同学的编号。

输出格式：

一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出。

输入输出样例

输入样例#1：

输出样例#1：

说明

对于的数据，；对于全部的数据，。

2005提高组第三题

题解：

本题有一个坑，那就是移动的人不需要连续。然后。。。知道这个坑点之后，我们很容易想到最优解，那就是化环为链，构建目标链与初始链，然后找到目标链与初始链中不一样的人的总数，用总人数相同的人数就是需要调换的人数。至于为什么能够在内完成操作，下图可以做一个更加直观的说明。

例如，初始环是左边的这个环，目标环是右边的环，如箭头所示的路径，我们可以通过的指令完成变换。

但是，环是可以旋转的，因此我们并不知道怎样转动是最优的。我们便可以考虑以每个点为起点进行搜索，因此，一个~~绝佳的~~ 的算法便出炉啦！

无疑，这个算法会让我们看到一片。所以，我们便可以考虑优化这个算法。如上图，我们从开始构建一条初始链，再构建一条目标链。

初始链：

目标链：

我们将两条链对应的数相减，取绝对值，便可以得到：

差值：

在这条差值中，出现的次数的是最多的。那么，若果有一条差值出现的次数是最多的，那么，这意味着什么？无疑，将那条链转动个单位，我们便可以得到最优解了！而在程序中，我们并不需要真正转动，只需要统计出现次数最多的差值，这就代表初始环在转动个单位之后，在同一个位置上的人数与目标环重合的最多，然后用总人数减去差值出现总次数，便是我们需要调换的人的数w量，也就是我们想要的答案啦！

等等！

这既然是一个环，那么，会不会构建目标链得到的结果不一样呢？的确是这样滴。还是以上图为例，从开始我们可以得到与两条链。那这怎么办呢？既然我们不确定我们拥有的目标链是顺时针构建的还是逆时针构建的，我们便可以在计算差值时顺时针与逆时针各跑一边，然后取最大值。我们用数组存储目标链，用数组存储初始链，便可以用顺时针从跑一遍，再用逆时针从跑一遍差值，然后找出最大的差值。

那么，什么时候不能符合每个同学的愿望呢？其实，只要构出目标环，便一定可以~~用玄学的方法~~使每个同学满意。那么，只有在构不成目标环的时候才输出。那什么时候构不成目标环呢？无疑，第个同学想挨着的那个人不想挨着他~~（好一个悲伤的故事）~~的时候才构不成环，此时输出。所以，我们直接判断第个同学左右两边是否还有空座就可以，如果没有的话，那就。。。输出了。

最后附上代码：

#include <iostream>
using namespace std;
int target[50001], initial[50001], people[50001][3], pluss[50001], minuss[50001]; //存储目标链，初始链，每个人最希望相邻的两个同学的编号，正序相同人数以及逆序相同人数
inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch=='-')
            w=-1;
    ch=getchar();
    }
    while(ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
int main() {
    int n;
    n = read();
    for (int i = 1; i <= n; i++) //读入编号是 i 的同学最希望相邻的两个同学的编号
        people[i][1] =read(), people[i][2] = read();
    target[1] = 1;
    target[2] = people[1][2]; //构建目标链
    initial[1] = 1;
    initial[n] = n; //构建初始链
    for (int i = 2; i <= n - 1; i++) {
        initial[i] = i; //构建初始链
        if (target[i - 1] == people[target[i]][1])
            target[i + 1] = people[target[i]][2];
        else if (target[i - 1] == people[target[i]][2])
            target[i + 1] = people[target[i]][1]; //构建目标链
        else{
            cout << -1 << endl; //第 i 个人希望相邻的人旁边没有空位了，无法构建目标链（一个悲伤的故事）
            return 0;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        pluss[(target[i] - initial[i] + n) % n]++; //顺时针从 1 ~ n 跑一遍
        minuss[(target[i]- initial[n - initial[i] + 1] + n) % n]++; //逆时针从 n ~ 1 跑一遍差
    }
    for (int i = 0; i <= n - 1; i++)
        ans = max(ans, max(pluss[i], minuss[i])); //找差值人数最多的
    cout << n - ans; //总人数 - 不用移动的人数 = 需要移动的人数，也就是答案
    return 0;
}

题目描述

输入输出格式

输入输出样例

说明

题解：

初始链： 1, 2, 3, 4, 5, 6

目标链： 1, 6, 3, 4, 2, 5

差值： 0, 4, 0, 0, 3, 1

等等！

初始链：

目标链：

差值：