CF1754B

_M1Ku_ · 2022-10-25 20:32:18 · 题解

题目大意

共有 t 组测试数据，每组测试数据中有一个整数 n，请求出一个排列，由 1 , 2 , 3 , 4 ,\cdots n 组成，使这个排列相邻的两元素的最小的差的绝对值最大。

即：

求一个 1\sim n 的排列 p，使得

最大。

解题过程

看到这种题如果没有思路（或者无法冷静思考）

可以多推几组答案（或写个暴力程序）

（注意，当 n 为奇数时可以有多种排列情况）

为了练习分析能力，我构造了一种较为一般的情况

不难发现，答案中的排列顺序是按照n的奇偶来分类讨论的，而且很容易就可以发现规律。

具体情况如下：（为了方便起见，用 s 来表示答案序列）

当 n 为偶数时，

2. 下一组排列的第一个元素为 \dfrac{n}{2}-1，第二个元素为 \dfrac{n}{2}-1+\dfrac{n}{2} \cdots 。

我们已经发现了简单的规律，可以用循环来实现。

当 n 为奇数时，

2. 接下来是从 n 开始两两一组的排列，用 i 来表示第 i 组排列。第 i 组排列的第一个元素为 n-i+1，第二个元素为 n-i- \left \lfloor \dfrac{n}{2} \right \rfloor ；

在比赛的过程中我们推出规律已经可以结束了。

下面是这样构造的原因

我们不难发现，无论我们怎么构造这个最大的最小值始终为\left \lfloor \dfrac{n}{2} \right \rfloor。

那么我们是每组相邻的连个元素的差为 \left \lfloor \dfrac{n}{2} \right \rfloor 即可，即：\left \{ x,x+\left \lfloor \dfrac{n}{2} \right \rfloor \right \} 满足我们在上面发现的规律。

现在我们需要解决相邻两组的差：

1. 当 n 为偶数时，很简单就可以发现，将每组的第一个元素从大到小排列即可；

2. 当 n 为奇数时，可以有多种合法的情况，可以把 n 放在两端，或者是中间的位置。最简单的就是放在开头或者是末尾，至此，我们发现可以优化我们之前所发现的较为复杂的规律。

总结

1. 如果你发现了构造方式，可以用手推答案规律来验证你构造方式的正确性

2. 如果你推出了规律，也可以冷静思考这个规律的原因

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<climits>
using namespace std;
int read() {
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-') 
            w = -1;
        ch = getchar();               
    }
    while (ch >= '0' && ch <= '9') {  
        x = x * 10 + (ch - '0');  
        ch = getchar();
    }
    return x * w;  
}
int n,t;
int main()
{
    t=read();
    while(t--)
    {
        n=read();
        if(n%2==0)
        {
            int mid=n>>1;
            for(int i=mid;i>=1;i--)
            {
                printf("%d %d ",i,i+mid);
            }
        }
        else
        {
            int mid=((n-1)>>1);
            for(int i=mid;i>=1;i--)
            {
                printf("%d %d ",i,i+mid);
            }
            printf("%d",n); //在末尾加上n
        }
        printf("\n");
    }
    return 0;
}