P9578题解

· · 题解

题意

给定一个正整数 n，你需要构造一个 n 的环形排列，最小化排列中任意相邻两数的和的最大值与最小值的差。

从任意数开始顺序输出这个排列。

思路

我们首先最小化最大值，此时 n 的左右只能为 1 和 2，那么最大值就是 n+2。

接着最大化最小值，同理，1 的左右只能是 n 和 n-1，恰好不与最大值最小的情况矛盾。

再思考一种可行的构造方法，由于是环形，可以将 1 与 n 置于两端，此时可以确定 n-1 位于第 2 位，2 位于第 n-1 位。于是就有了一种大胆的猜测，不断将和为 n+1 的一对数分别置于两端，第一个数为偶数时交换这对数的位置。

对于任意一个数，可以证明，其与它相邻数的和恰为 n 及 n+2，满足要求。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int a,b[1000010];
signed main() {    
    cin>>a;
    int l=1,r=a;
    while(l<=r){
        if(l%2==1){
            b[l]=l;
            b[r]=r; 
        }else{
            b[r]=l;
            b[l]=r;
        }
        l++;
        r--;
    }
    for(int i=1;i<=a;i++){
        cout<<b[i]<<" ";
    }
    return 0;
}
//1 7 3 5 4 6 2 8