#模拟#洛谷 1338 末日的传说

本文主要是介绍#模拟#洛谷 1338 末日的传说，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

就是求$1\sim n$排列逆序对总数为$m$，字典序最小

---

分析

一开始最大逆序对总数为$n\ast (n-1)/2$ ($n$个位置)
首先如果当前最大逆序对总数不少于$m$，就把最小数插入当前最前的位置，否则插入当前最后的位置，$m$减去最小数产生的逆序对总数。

---

代码

#include <cstdio>
using namespace std;
int n,m,a[50001];
int main(){scanf("%d%d",&n,&m);int r=n,l=1;for (int i=1;i<=n;i++){long long t=(long long)(n-i)*(n-i-1)/2;if (t>=m) a[l++]=i;else a[r--]=i,m-=(r-l+1);} for (int i=1;i<=n;i++) printf("%d ",a[i]);return 0;
} 

这篇关于#模拟#洛谷 1338 末日的传说的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---