CF1743B Permutation Value 题解

sw2022 · 2022-10-20 09:52:01 · 题解

题意简析

给定一个排列的长度 n，构造一个排列，最小化这个排列的子段中是排列的子段数量。因为对于任意一个长度为 k 的排列，它的子段中是排列的子段都至少包含 \{1\} 和整个排列，所以只要使得这个排列中没有其他满足条件的子段即可。当 n=1 时，显然排列只有一种可能。\forall n\ge 2，只需要把 1 置于排列的开头，2 置于排列的结尾，满足条件的子段一定只有 \{1\} 和整个排列，可得数量为最小值。

代码/解释

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,n,i;
    cin>>t;
    while(t--)
    {
        cin>>n;
        printf("1 ");
        for(i=n;i>=2;i--)
        printf("%d ",i);
        cout<<endl;
    }
    return 0;
}