Codeforces Round 640 (Div. 4) G. Special Permutation

发布时间:2024年01月06日

题目链接:Problem - 1352G - Codeforces?

题意:给你一个数n,请你构造长度为n的排列(1-n中每个数字都要出现一次),使得相邻的两个数之间差的绝对值在2-4之间。

?

先看一下什么情况下我们无法构造出这样的序列。题目样例中2是已知无法构造的,我们尝试3,发现也无法构造,从4开始似乎每一个都可以构造。

我们尝试这是怎么构造出来的,当看到相差为2时,第一瞬间想到的是奇偶性相同的顺序序列

例如:

1,3,5,7,9......

2,4,6,8,10......

现在我们只用解决如何将这两个序列连接起来,因为相差为2-4,要求奇偶性不同,那么连接的这两个数就只能相差3,即用 9 - 3? 去连接,然后在从10输出,6和10相差为4,如果偶数最高项是8,那么就从8输出。不管是10还是8相差就在2-4区间内。

#include <bits/stdc++.h>
#define int long long 

using namespace std;
int n ;

void solve()
{
    cin >> n ;  
    if(n <= 3) puts("-1") ;
    else if(n == 4) puts("3 1 4 2 ") ;
    else
    {
        for(int i = 1 ; i <= n ; i += 2)
            cout << i << " " ;
        int x , y ;
        if(n % 2) x = n , y = n - 1 ;
        else x = n - 1 , y = n ;
        
        cout << x - 3 << " " ;
        x -= 3 ;
        for(int i = y ; i >= 2 ; i -= 2)
            if(i != x) cout << i << " " ;
        puts("") ;
    }
}

signed main()
{
    int t ;
    cin >> t ;
    while(t --)
    {
        solve() ;
    }
    return 0 ;
}

文章来源:https://blog.csdn.net/weixin_50089904/article/details/135398289
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。