CSU_1674_KSwapOperation

1674: K swap operation

Time Limit: 1 Sec   Memory Limit: 128 MB   Special Judge

Submit: 10   Solved: 9

[ Submit][ Status][ Web Board]

Description

最近Mr.Q想要隻通過一種操作來對序列進行升序排序，該操作是“交換相鄰的兩個數”，聰明的Mr.Q總是會選擇最優的方法進行操作，也就是說他使用的交換次數是最少的。比如對于對于序列：

2 3 1 4

Mr.Q會使用2次交換操作。

而對于序列：

4 3 2 1

Mr.Q會使用6次交換操作。

請你構造一個1~N的排列，使Mr.Q剛好使用 K 次操作将它按升序完成排序。

Input

第一行一個整數T（T≤50），表示資料組數。

接下來每組輸入資料占一行，包含一個非負整數K（0≤K≤10^9），含義如題中描述。

Output

對于每組資料你應該輸出2行，假如存在多組方案，輸出任意一種即可。

第一行一個整數N（1≤N≤10^5），表示你構造的排列長度。

第二行輸出你構造的排列，相鄰兩個數之間用一個空格隔開，請確定每個數都在你構造的排列中隻出現1次，并且都處于範圍[1,N]内。

請不要輸出多餘的空格或數字，否則有可能會WA的。

Sample Input

2
0
6      

Sample Output

3
1 2 3
4
4 3 2 1      

HINT

Source

0909122215

一個構造問題，機智不算機智，水不，好吧……算水

構造一個數串使其逆序數為k就好，構造方法很多

我的方法是始終構造一個長度為100000的數串（應該是這個串太長導緻我的程式跑的比較慢）

然後整個串倒過來100000 99999 99998 99997…… 1可以得到 99999+99998+……+1的逆序數，滿足題目要求

然後每把一個前面的數挪到後面，後面為順序，則可以消除挪的這個數-1的逆序

是以程式如下

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
 
const int M=1e5+5;
int hou[M];
 
int main()
{
    int t;
    int num;
    scanf("%d",&t);
    //freopen("2.out","w",stdout);
    while(t--)
    {
        int pr=0;
        scanf("%d",&num);
        memset(hou,0,sizeof(hou));
        for(int i=1e5-1;i>0;i--)
        {
            if(!num)
                break;
            if(num>=i)
            {
                num-=i;hou[i+1]=1;
            }
        }
        printf("100000\n");
        for(int i=1e5;i>=1;i--)
        {
            if(hou[i])
            {
                pr++;
                if(pr!=1e5)
                   printf("%d ",i);
                else
                    printf("%d\n",i);
            }
        }
        for(int i=1;i<=1e5;i++)
        {
            if(!hou[i])
            {
                pr++;
                if(pr!=1e5)
                   printf("%d ",i);
                else
                    printf("%d\n",i);
            }
        }
    }
    return 0;
}