首页 > 其他 > 详细

洛谷p1338末日的传说(思维好题,数学)

时间:2018-11-10 20:51:26      阅读:136      评论:0      收藏:0      [点我收藏+]

题目链接:https://www.luogu.org/problemnew/show/P1338

 

题目暴力全排列是肯定不行的。

比较难想啊,关键抓住字典序小也就是小的数尽量往前排,找剩余的逆序对数!

 

思考逆序对数需要用到数学排列组合的知识,长度为n的序列最多有n(n-1)/2个逆序对,组合数知识一算就知道。

还需要long long才过= =

 1 #include <iostream>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn=1e5+5;
 5 ll a[maxn];
 6 ll n,m;
 7 
 8 int main()
 9 {
10     ios::sync_with_stdio(false); cin.tie(0);
11     
12     cin>>n>>m;
13     
14     ll last=n,first=1;
15     for(int i=1;i<=n;i++)
16     {
17         int t=(n-i)*(n-i-1)/2;//长度为n的序列最多有这么多对
18         
19         if(t>=m) a[first++]=i;//放开头
20         else 
21         {
22             a[last--]=i;
23             m=m-(last-first+1);//放最后
24         }
25     }
26     
27     for(int i=1;i<=n-1;i++) cout<<a[i]<< ;
28     cout<<a[n]<<endl;
29     
30     return 0;
31 }

 

完。

洛谷p1338末日的传说(思维好题,数学)

原文:https://www.cnblogs.com/redblackk/p/9940374.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!