[ACM_模拟] ZJUT 1155 爱乐大街的门牌号 (规律 长为n的含k个逆序数的最小字典序)

  1. 云栖社区>
  2. 博客>
  3. 正文

[ACM_模拟] ZJUT 1155 爱乐大街的门牌号 (规律 长为n的含k个逆序数的最小字典序)

史迪奇2号 2017-12-13 14:56:00 浏览703
展开阅读全文


Description

 

ycc 喜欢古典音乐是一个 ZJUTACM 集训队中大家都知道的事情。为了更方便地聆听音乐,最近 ycc 特意把他的家搬到了爱乐大街(德语Philharmoniker-Straße)。在爱乐大街上,依次坐落着N座跟音乐有关的建筑,比如音乐厅、歌剧院等建筑。走在爱乐大街的路上,ycc 感到非常满意。过了一会儿,ycc 开始对这些建筑的门牌号产生了兴趣,这 N 个建筑各自有唯一的门牌号,范围从 1 到 N 。不过大概住在爱乐大街上的人都比较文艺,不喜欢循规蹈矩,他发现爱乐大街的门牌号并不是按照空间顺序依次从 1 到 N 的,而是任意顺序的,而且似乎没有什么规律可循。
ycc 不太习惯,于是他在纸上依次记录了每个建筑的门牌号,将他们写成一列。然后他在纸上开始比划起来。他发现门牌序列的逆序对个数为 K 。什么是逆序对呢?简单地说,就是两个门牌号,号码小的门牌号在号码大的门牌号后面。比如假设 N = 4 ,且门牌号序列是 1 3 4 2 ,那么这个序列的逆序对就有 (4, 2)  (3, 2) 两对,也就是说逆序对个数 K = 2 。那么现在,告诉你爱乐大街的建筑个数 N 和序列的逆序对个数 K,你知道爱乐大街的门牌号序列是怎么样的吗?

Input

 

第一行一个整数 T ,表示有 T 组数据。
每组数据有两个整数 N (1  N  105 K (0  K  N(N - 1) / 2  K  108,分别表示爱乐大街上的建筑个数和门牌号序列的逆序对个数。

Output

 

在一行中输出空格隔开的 N 个数(行末没有空格),表示原来的门牌号序列,每组数据占一行。若有多个序列满足要求,则输出字典序最小的序列。

Sample Input

 

3
5 1
4 2
2 0

Sample Output

 

1 2 3 5 4
1 3 4 2

 
题目大意:给一个N个自然数(1-N),要求找出逆序对数为K的最小字典序排列的那一个排列方式  

解题思路:想要最小字典序那么前面的数字就尽量少的向后面去,因此先计算出满足K个逆序数最少需要LMMN位数字(也就是后LMMN要调动) ②\又因为剩下的数字第一位要尽量小,所以剩下的LMNN-1个数必然倒序排列。③\又因为后LMMN-1个数倒序排列有NXN=(LMMN-1)*(LMMN-2)/2个逆序数,所以剩下数字的第一位的逆序数为K-NXN ④\所以可以确定剩下数字的排列方式。

复制代码
 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 using namespace std;
 5 int getLastMostMoveNum(int k){
 6     return (int)ceil((1.0+sqrt(1.0+8*k))/2);
 7 }
 8 int getNumOfNiXu(int k){
 9     return k*(k-1)/2;
10 }
11 int main(){
12     int T;cin>>T;
13     while(T--){
14         int N,K,i;
15         cin>>N>>K;
16         if(K==0){//顺序输出即可
17             for(i=1;i<N;i++)
18                 cout<<i<<' ';
19             cout<<N<<'\n';
20         }else{//存在逆序对
21             int LMMN=getLastMostMoveNum(K);//计算后LMMN位要变化顺序
22             for(i=1;i<=N-LMMN;i++)//输出前面不用调序的序列
23                 cout<<i<<' ';
24             int Last[100005];//保存剩下的数字
25             for(int j=0;i<=N;j++,i++)Last[j]=i;
26             int NXN=getNumOfNiXu(LMMN-1);//计算LMMN-1个数完全逆序的逆序数NXN
27             //所以要用后LMMN位组成K个逆序数就要把Last[K-NXN]放到第一位,其他完全倒序
28             cout<<Last[K-NXN];
29             for(int j=LMMN-1;j>=0;j--)if(j!=K-NXN)cout<<' '<<Last[j];
30             cout<<'\n';
31         }        
32     }return 0;
33 }
复制代码


网友评论

登录后评论
0/500
评论