逆序对 模拟贪心

题目：

Inversion逆序数对
(inversion.cpp/in/out 1s 256M)
给定N的值，要求找出一个N的全排列，这个全排列中，逆序数有M对。这样的结果会存在多个解，现在请输出字典
序最小的那个解。例如当输入3 1 时，则1 3 2这个排列有一个逆序对，2 1 3这个排列同样也有一个逆序对。但
1 3 2这个字典序更小，因而其是正解。
Input
每组数据给出N，M。1 <= n <= 50000 and 0 <= m <= 1/2*n*(n-1).
整个测试以-1 -1代表结束。
Output
如题
Sample Input
5 9
7 3
-1 -1
Sample Output
4 5 3 2 1
1 2 3 4 7 6 5

可以知道如果有1个数字参加逆序对，则最多0个。
可以知道如果有2个数字参加逆序对，则最多1个。
可以知道如果有3个数字参加逆序对，则最多3个。
可以知道如果有4个数字参加逆序对，则最多6个。
可以知道如果有5个数字参加逆序对，则最多10个。
则我们可以利用从N开始倒过来的若干个数字来构成逆序数对，再进行适当的微调就好了。

先预处理，在不断的微调模拟即可。

code：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 long long n,m,a[50001];
 4 int main()
 5 {
 6     for(int i=1;i<=5000;i++){
 7         a[i]=i*(i-1)/2;
 8          //cout<<"a[i]= "<<a[i]<<endl;   
 9     }
10     while(cin>>n>>m&&n!=-1)
11     {
12         for(int i=1;i<=n;i++)
13             if(a[i]>m)
14             {
15                 //cout<<"i= "<<i<<" a[i]= "<<a[i]<<" n= "<<n<<endl;
16                 int f=0;
17                 for(int j=1;j<=n-i;j++)
18                     cout<<j<<" ";//<<endl;
19                 cout<<n-(a[i]-m)<<" ";
20                 for(int j=n;j>=n-i+2;j--)
21                 if(j==n-a[i]+m)
22                 {
23                     f=1;
24                     continue;
25                 }
26                 else cout<<j<<" ";
27                 if(f)cout<<n-i+1;
28                 cout<<endl;
29                 break;
30             }
31     }
32     return 0;
33 }
34 /*
35 5 9
36 7 3
37 -1 -1
38 */