Inversion
|
Time Limit: 1000MS |
|
Memory Limit: 30000K |
|
Total Submissions: 2631 |
|
Accepted: 1143 |
Description
The inversion number of an integer sequence a1, a2, . . . , an is the number of pairs (ai, aj) that satisfy i < j and ai > aj . Given n and the inversion number m, your task is to find the smallest permutation of the set { 1, 2, . . . , n }, whose inversion number is exactly m.
A permutation a1, a2, . . . , an is smaller than b1, b2, . . . , bn if and only if there exists an integer k such that aj = bj for 1 <= j < k but ak < bk.
Input
The input consists of several test cases. Each line of the input contains two integers n and m. Both of the integers at the last line of the input is −1, which should not be processed. You may assume that 1 <= n <= 50000 and 0 <= m <= n(n − 1)/2.
Output
For each test case, print a line containing the smallest permutation as described above, separates the numbers by single spaces.
Sample Input
5 9
7 3
-1 -1
Sample Output
4 5 3 2 1
1 2 3 4 7 6 5
Source
/*
找了好久规律,晕了好多次,改了又写,写了又改,终于找出来了,这个问题主要基于以下考虑:
对于任意一个序列i, i + 1, ..., j其最大的inversion number是全部逆序的情况,即
j, j - 1, ..., i + 1, i,值记为in(i, j) = (j - i + 1) * (j - i) / 2
所以这个问题的解决的步骤如下:
(1)对于输入n, seq, 从后往前考虑找到可以涵盖seq值的i, 即in(i, n) >= seq
(2)由(1)可知,i -> n足够用来表示值为seq的insersion number,所以1-> i - 1只要按照
升序打印即可
(3)剩下的i -> n如何表示值为seq的逆序数呢?考察几个例子不难发现.剩下的i -> n的形式
一定是 k, v1, v2, ..., vn-1,其中k为i->n中的任意一个数, {v1, v2, v3, ..., vn-1}是
除k以外剩下的数的完全逆序形式.例如:加入i = 5, n = 10, {7, 10, 9, 8, 6, 5}就是这样
一种形式.那么剩下的任务就是找出这个k即可.由上述分析我们不难列出方程式:
k - i + (n - i) * (n - i - 1) / 2 = seq, 其中k - i表示大头的k对这个数列逆序的贡献
数, (n - i) * (n - i - 1) / 2表示剩下的除k以外的i->n完全逆序数列的贡献度,这样把k
解出来即可.
*/
#include <iostream>
using namespace std;
int main()
{
int n, seq, i, j;
while(scanf("%d%d", &n, &seq) && (n + seq) != -2)
{
int total = 0;
for(i = n; i >= 1; i--)
{
total += n - i;
if(total >= seq) break;
}
for(j = 1; j < i; j++) printf("%d ", j);
int k = seq + i - (n - i) * (n - i - 1) / 2;
printf("%d ", k);
for(j = n; j >= i; j--)
if(j != k)
printf("%d ", j);
printf("\n");
}
return 0;
}
