网易笔试4.11 第三题 错排

设序列为

当n为偶数时，很显然，相邻的两两交换，即与交换，与交换，以此类推生成错排。这样代价是最小的，因为错排与原排序中每个元素的距离都为1，代价为。

当n为奇数时，我们分情况。

设奇数位最小的为，x为对应的下标；偶数位最小的为，y为对应下标。

首先需要明确的一点是，n为奇数时，我们无法再通过类似n为偶数的情况，把相邻数对两两交换，因为必然会有一个是剩下的。剩下的这个，无论如何，在错排中与原排列的距离都会大于1。

若，最小的V在奇数。那么以下标x为分界条件，将错排分成三部分，后半部分为n-x个，且n-x为偶数，可以直接采用相邻交换的方式，这部分的距离都为1。而取x-2，x-1，x三个位置，作为中间部分，将其分别左移，则序列由原来的变为。除了的距离为2，其余都为1。对剩下的1~x-3同理，这部分为偶数个，距离都为1。反过来同理。

这种情况下，那个被剩下的距离不为1的元素，有着最小的V值，同时距离仅仅为2。很显然答案为。

若，最小的V在偶数位。此时我们再以下标y为分界条件，对错排进行划分。

若我们同样分成3部分，若让中间部分为奇数个。则此时，若不在中间部分的边缘，即是类似，那么无论是左移还是右移生成的错排序列，本身的距离都会为1，而有一个奇数位的边缘数字距离变为2。此时若该边缘数字为，则花销为。若不是则只会更大。

若是在边缘，类似，则此时前后部分必定为奇数个，必然会有某个的距离大于1，则总花销肯定大于。

若让中间部分为偶数个，则前后部分必然为奇数个。那么对其中任一部分，必然会有某个的距离大于1，则总花销肯定大于。

那么对最小的V在偶数的情况，可以分成两部分吗？同样的，若在边缘，比如在前半部分的末尾，如，则后半部分为奇数个，会存在某个的距离大于1，让总花销大于等于。若不在边缘，前半部分如。此时后半部分为偶数个，距离都为1。但对于前半部分，若采取左右移动的方式，总是边缘数字的距离为2，那么花销也是大于等于。至于其它的生成错排的方式，距离只会更大。

所以对于的情况，即最小的V在偶数位，开销也是必然大于等于，而采用跟时类似的划分就可以得到该下界了。

综上，

n为偶数，答案为。

n为奇数，答案为，其中为奇数位上最小的V值。

不保证证明正确，欢迎讨论。

其它两题就不放题解了。

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 20 + 5;
int main()
{
    // freopen("in.txt", "r", stdin);
    int T;
    int n, x;
    cin >> T;
    while (T--)
    {
        int min_odd;
        long long sum = 0;
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> x;
        cin >> sum;
        min_odd = sum;
        for (int i = 2; i <= n; ++i)
        {
            cin >> x;
            sum += x;
            if (i & 1 != 0)
                min_odd = min(min_odd, x);
        }
        if (n & 1)
            cout << sum + min_odd << endl;
        else
            cout << sum << endl;
    }
    // fclose(stdin);
    return 0;
}