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
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章