P9578 「Cfz Round 1」Permutation 题解

· · 题解

题意（我尽量不用太多数学式子）

定义一个函数 f(\{x_n\})，是求一个序列相邻两项（首尾相邻）的和最大值减最小值。

你需要构造一个元素为 1 到 n 的排列。使得它是所有元素为 1 到 n 的排列对 f 函数求值最小的。

思路

观察数据范围，提示我们可以奇偶数分别考虑，暴力构造 n=3 到 n=10。

奇数

下标为奇数 正着枚举 是 1 ,2 ,4 ,6 ,8 ,...，为偶数 反着枚举 是 3 ,5 ,7 ,9 ,...。

可以构造数组 a，a_1 \leftarrow 1，其他奇数下标 a_i \leftarrow i-1。下标为偶数 a_i \leftarrow n-i+2。

偶数

对半分左边一半下标为奇数的与它们相对称的都为下标本身。

对半分左边一半下标为偶数的与它们相对称的相加为 n+1，且左边一半第一个元素为 n-1， 正着枚举 每次递减 2，右半边倒数第二个元素为 2，反着枚举 每次递增 2。

*正着枚举是指从 1 到 n 枚举，反着枚举是指从 n 到 1 枚举 。

可以构造数组 a 下标为偶数 a_i \leftarrow x\ ,\ a_{n-i+1}\leftarrow n+1-x，且每次 ,x\leftarrow x+2。其余 a_i\leftarrow i。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005];
int main(){
    cin>>n;
    if(n%2==0){
        for(int i=2,j=n-1;i<=n/2;i+=2,j-=2){
            a[i]=j;
            a[n-i+1]=n+1-j;
        }
        for(int i=1;i<=n;i++){
            if(!a[i]){
                cout<<i<<" ";
            }else{
                cout<<a[i]<<" ";
            }
        }
    }else{
        a[1]=1;
        for(int i=3,j=2;i<=n;i+=2,j+=2){
            a[i]=j;
        }
        for(int i=2,j=n;i<=n;i+=2,j-=2){
            a[i]=j;
        }
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" ";
        }
    }
    return 0;
}