拼多多 2020校招 多多的排列函数（找规律 构造）

数列 {An} 为N的一种排列。

例如N=3，可能的排列共6种：

定义函数F:

其中|X|表示X的绝对值。

现在多多鸡想知道，在所有可能的数列 {An} 中，F(N)的最小值和最大值分别是多少。

解题思路：

我们发现，只要把连续的4个数倒着放，就可以得到F(x)=0，比如 9 8 7 6，那么F(4)=0.所以考虑最小值的时候，我们连续4个数4个数的来放，想方法让F(n)==0. 那么我们试着来进行构造：

n%4 == 0 : 输出0 按照上面说的比如 N = 8；那么我们 4 3 2 1 9 8 7 6 每4个周期进行构造即可。

n%4 == 1 : 输出1 我们让最后一个数放1即可。比如N = 9；那么我们可以 9 8 7 6 5 4 3 2 1

n%4 == 2: 输出 1 我们最后两个数字放 2 1 即可。

n%4 == 3:输出0；这个我们可以看样例，最后数字放3 1 2 即可。

现在我们来构造最大值。

首先最大值肯定不超过N。

那么同样地，我们4个4个来放。

n%4 == 0:输出N。最后的4个数我们这样放即可：3 2 1 N

n%4 == 1:输出 N。最后一个数字我们放入N.

n%4 == 2 :输出N-1.最后放入：1 N 即可

n%4==3:输出 N-1.最后放入：1 2 N即可

#include <bits/stdc++.h>
using namespace std;
int main(){
    int cas;cin>>cas;
    while(cas--){
        int n;cin>>n;
        int N=n;
        if(n%4 == 0)cout<<0<<" "<<N<<endl;
        else if(n %4 == 1)cout<<1<<" "<<N<<endl;
        else if(n%4==2)cout<<1<<" "<<N-1<<endl;
        else cout<<0<<" "<<N-1<<endl;
    }
    return 0;
}