csu oj K swap operation 模拟

                                         K swap operation

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

题意：对于给定的数字k，求一序列，该序列要变成升序序列需要的最小的交换次数为k

题解：这是一道模拟题。。。

1.因为对于任一长度为n的倒序序列，要变为升序序列则最少的交换次数为n*(n-1)/2,   只要找到最小的n （长度） 问题就能迎刃而解，   那么对于输入数据k，也就是找到一个最小的整数n使得n*(n-1)>=k，

2.对于多出来的交换次数下面举个例子：

     若输入k=7

     可求得最小的n为5；

     对于一个倒序且长度为5的数串，5 4 3 2 1，若变为升序 最小的操作次数为5*4/2=10；

     10-7=3 （3为多出来的交换次数）？？？怎么办呢？？

     因为可以知道10次交换为 ： 54312,   54132,   54123,   51423,   51243,   51234,   15234,   12534,    12354,   12345;

     其中3+1=4为了跑到后面需要移动3次。。。

     那么就直接把他放在后面就好。。。

     序列变为：5 3 2 1 4 

     7次交换为：53124,  51324,  51234, 15234, 12534, 12354, 12345;

#include<cstdio>
#include<cmath>
int main()
{  int n,m;
    scanf("%d",&n);
    while(n--){
        scanf("%d",&m);
        int i;
        if(m==0)
        {
            printf("3\n");
           for(i=1;i<3;i++) printf("%d ",i);
           printf("3\n");
        }
        else {
            int a,i;
            a=(int)sqrt(2*m);
            for(i=a;i<a+3;i++){
                if((i*(i+1))>=2*m) {
                    break;}
            }
            a=i+1;
            int div=(int)a*(a-1)/2;
            int sub=div-m;;
            printf("%d\n",a);
            for(i=a;i>sub+1;i--) printf("%d ",i);
            for(i=sub;i>=1;i--) printf("%d ",i);
            printf("%d\n",sub+1);
        }
    }
    return 0;
}
           

注意输出格式。。。