1263 末日传说

1263 末日传说

末日传说 Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByte Description 只要是参加JSOI活动的同学一定都听说过汉诺塔的传说：三根柱子上的金片每天被移动一次，当所有的金片都被移完后，世界末日也就随之降临了。 在古老东方的幻想乡，人们都采用一种奇特的方式记录日期：他们用一些特殊的符号来表示从1开始的连续整数，1表示最小而N表示最大。创世纪的第一天，日历就被赋予了生命，它自动地开始计数，就想排列在不断地增加。 我们用1-N来表示日历的元素，第一天日历就是： 1,2,3，…N 第二天，日历就变为： 1,2,3，…N，N-1 每天它都生成一个以前未出现过的“最小”的排列——把它转为N+1进制后数的数值最小。 日子一天天过去。有一天，以为预言家出现了——他预言道，当这个日历到达某个上帝安排的时刻，这个世界就会崩溃……他还预言道，假如某一个日期的逆序数达到一个值M的时候，世界末日就要降临。 什么是逆序？日历中的两个不同符号，假如排在前面的那个比排在后面的那个更大，就是一个逆序，一个日期的逆序总数达到M后，末日就要降临，人们都期待一个贤者，能够预见那一天到底什么时候到来。 Input 输入文件只包含一行两个正整数，分别为N（N<=50000）和M。 Output 输出一行，为世界末日的日期，每个数字之间用一个空格隔开。 Sample Input 5 4 Sample Output 1 3 5 4 2

题意：

组合逆序数

题解： 暴力：O(N) 优化： 若第一个位置放x，则一定产生x-1个逆序对，无论1..x-1的具体位置在哪里。第二个位置放除去x后第x2小的数，也必然产生x2-1个逆序对。以此类推，可以得出： n个数的逆序对总数=sigma(xi-1) 于是，题目转化为求一组xi满足逆序对总数=M,且这组xi对应的全排列字典序最小。 字典序最小，即使前面的xi尽量小。故逆序对集中在最后。 具体构造方法：前面递增，不产生逆序对，后面递减，让尽量少的数产生最多的逆序对。显然k个数递减形成的逆序对为k(k-1）/2,因此可以让xi=1（i=1...N-k-1，从1开始递增),后面xi=N-i+1（i=N-k+1...N,从N开始递减），Xn-k=n-k+(M-k*(k-1)/2+1)-1。 N个数最多的逆序对为O（N^2)，因此M应为long long！

AC：

#include#include#include#include#include#includeusing namespace std;typedef long long LL;//令xi为当前未选元素中第xi小 求sigma(xi-1)=m的最小序列//令整个序列先升后降 则k(k-1)<=m的最大的k应为下降序列的个数 LL N,M;int main(){ int j=0; int a[50001]={0}; cin>>N>>M; int k=(int)((1+sqrt(1.0+8*M))/2); int p=M-k*(k-1)/2+1; for(int i=1;i0) printf("%d ",N-k+p-1); //Xn-k=n-k+(M-k*(k-1)/2+1)-1。 for(int i=N;i>=N-k && i>0;i--) if(i!=N-k+p-1){ a[++j]=i; } for(int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。