大概题意:
就是求 1 到 n 的排列中字典序最小的一个满足逆序对个数为m的排列。
分析:
首先我们要知道一个排列能有的最多逆序对 n*(n-1)*/2 即当他为严格递增序列时;而我们又知道逆序对越多该数列的字典序越大;因此可对题意这样分析,很明显从最小的数 ( i )开始考虑 如果除去该数 剩余的数 ( n - i ) 依然能构成大于等于m的逆序对 (n-i)*(n-i-1)/2>=m;可将该数放在最前面,否则 将它放在末端,此时的数既可以做出最大的贡献(构成了 n-i 个逆序对),更新m;
还有一点要注意啦!!!!!
因为数据是5e4,做乘法是会爆int 切记要 long long
详细见代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int maxn=5e4+5; 5 ll ma[maxn]; 6 int main() 7 { 8 ll n,m; 9 scanf("%lld%lld",&n,&m); 10 ll st=1,sk=n; 11 for(ll i=1;i<=n;i++) 12 { 13 ll t=(n-i)*(n-1-i)/2; 14 if(t>=m){ 15 ma[st++]=i; 16 } 17 else{ 18 ma[sk--]=i; 19 m-=(n-i); 20 } 21 } 22 for(ll i=1;i<=n;i++) 23 { 24 if(i==1){ 25 printf("%lld",ma[i]); 26 } 27 else{ 28 printf(" %lld",ma[i]); 29 } 30 } 31 printf(" "); 32 return 0; 33 }