题解 | #小美的排列构造#

这种题一看就有很强的规律性，不如打个表，python打表很方便，代码如下

if __name__ == "__main__":
    n = 6
    res = []
    diff = inf
    for p in permutations(range(1, n + 1)):
        mx = -inf
        mn = inf
        for a,b in pairwise(p):
            mx = max(mx, a + b)
            mn = min(mn, a + b)
        if mx - mn < diff:
            res = p
            diff = mx - mn
    print(res)

可以看看结果如下

    (1, 3, 2)
    (1, 4, 2, 3)
    (1, 5, 2, 4, 3)
    (1, 6, 2, 5, 3, 4)

发现就是一个顺序和逆序。那么答案就是：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
signed main() {
    close;
    int n; cin >> n;
    vector<int> a(n);
    int num = 1;
    for(int i = 0; i < n; i+=2) a[i] = num++;
    num = n;
    for(int i = 1; i < n; i+=2) a[i] = num--;
    for(auto i: a) cout << i << " ";
    return 0;
}

那么如何分析正解呢，对于 $n = 2$ ,显然为0。

对于 $n > 2$ 的情况：我们可以构造一个加1减1的序列，这样就能够保证绝对差肯定为1