自动搬运

查看原文

来自洛谷，原作者为

	Defy_HeavenS 世界上有两种程序员，一种是下标以0开始的，一种是下标以1开始的，我是第一种，请问我是下标为几的程序员

搬运于2025-08-24 22:49:47，当前版本为作者最后更新于2023-08-26 19:57:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

思路

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

奇数

• $n=3:1 ,3 ,2$。
• $n=5:1 ,5 ,2 ,3 ,4$。
• $n=7:1 ,7 ,2 ,5 ,4 ,3 ,6$。
• $n=9:1 ,9 ,2 ,7 ,4 ,5 ,6 ,3 ,8$。

下标为奇数 正着枚举 是 $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=4:1 ,3 ,2 ,4$。
• $n=6:1 ,5 ,3 ,4 ,2 ,6$。
• $n=8:1 ,8 ,3 ,5 ,4 ,6 ,2 ,8$。
• $n=10:1 ,9 ,3 ,7 ,5 ,6 ,4 ,8 ,2 ,10$。

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

对半分左边一半下标为偶数的与它们相对称的相加为 $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;
}