P1338 末日的传说网页链接P1338 末日的传说题目描述只要是参加 jsoi 活动的同学一定都听说过 Hanoi 塔的传说三根柱子上的金片每天被移动一次当所有的金片都被移完之后世界末日也就随之降临了。在古老东方的幻想乡人们都采用一种奇特的方式记录日期他们用一些特殊的符号来表示从1 11开始的连续整数1 11表示最小而n nn表示最大。创世纪的第一天日历就被赋予了生命它自动地开始计数就像排列不断地增加。我们用1 − n 1-n1−n来表示日历的元素第一天日历就是1 , 2 , … , n − 2 , n − 1 , n 1,2,\ldots,n-2,n-1,n1,2,…,n−2,n−1,n第二天日历自动变为1 , 2 , … , n − 2 , n , n − 1 1,2,\ldots,n-2,n,n-11,2,…,n−2,n,n−1······每次它都生成一个以前未出现过的“最小”的排列——把它转为n 1 n1n1进制后数的数值最小。日子一天一天地过着。有一天一位预言者出现了——他预言道当这个日历到达某个上帝安排的时刻这个世界就会崩溃······他还预言到假如某一个日期的逆序达到一个值m mm的时候世界末日就要降临。什么是逆序日历中的两个不同符号假如排在前面的那个比排在后面的那个更大就是一个逆序一个日期的逆序总数达到m mm后末日就要降临人们都期待一个贤者能够预见那一天到底将在什么时候到来输入格式只包含一行两个正整数分别为n nn和m mm。输出格式输出一行为世界末日的日期每个数字之间用一个空格隔开。输入输出样例 #1输入 #15 4输出 #11 3 5 4 2说明/提示对于10 % 10\%10%的数据有n ≤ 10 n\le10n≤10对于40 % 40\%40%的数据有n ≤ 1000 n\le1000n≤1000对于100 % 100\%100%的数据有n ≤ 5 × 10 4 n\le5\times10^4n≤5×104。所有数据均有解。解题思路本题需要构造字典序最小且逆序对恰好等于m mm的1 ∼ n 1\sim n1∼n排列。首先算出完全逆序排列的最大逆序对数采用贪心策略逐位构建序列优先依次放置较小数字每确定一位数就更新后续区间可提供的最大逆序对上限。若剩余所需逆序对m mm超出当前上限则调整当前位置的数值补齐差额该位置作为分界点之后将所有未使用数字倒序输出依靠倒序结构补足剩余逆序对。整体采用线性遍历构造时间复杂度O ( n ) O(n)O(n)可以高效处理n ≤ 5 × 10 4 n \le 5\times10^4n≤5×104的数据范围。总结核心逻辑贪心在前半段放最小数保证字典序分界点后倒序排列补足逆序对精准满足逆序对数量要求。关键操作计算全局最大逆序、逐位判断能否放置当前最小值、定位分界位置、后半段逆序输出。效率保障纯线性遍历无嵌套循环与复杂运算适配题目数据上限。代码简要说明先计算1 ∼ n 1\sim n1∼n完全逆序的最大逆序对数S作为初始剩余逆序容量。从前到后逐个确定排列元素每次扣除当前位选最小值时后续能提供的最大逆序。若m mm超过剩余容量计算当前位置应取的数值并标记已使用跳出遍历。最后从大到小遍历数字输出所有未标记的数依靠倒序生成剩余逆序对。布尔数组U用于标记已选用数字保证排列元素不重复。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,m,S,i,j,k;boolU[50005];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld%lld,n,m);S(n*(n-1))1;for(i1;in;i){S-(n-i);if(mS){printf(%lld ,im-S);U[im-S]true;break;}printf(%lld ,i);U[i]true;}for(jn,kn;ji;j--,k--){if(U[k]){j;continue;}printf(%lld ,k);}return0;}