UOJ278 【UTR #2】题目排列顺序 题解
题目链接：#278. 【UTR #2】题目排列顺序
题意：
“又要出题了。” 宇宙出题中心主任 —— cxy ，坐在办公桌前策划即将到来的 UOI。
这场比赛有 $n$ 道题， cxy 需要决定这些题目的难度，然后再在汪洋大海中寻找符合该难度的题目。
题目的难度可以用一个 $1$ 到 $n$ 的排列 $a_1, \dots, a_n$ 表示，其中 $a_i$ 表示第 $i$ 道题目在这 $n$ 道题目中是第 $a_i$ 简单的题目，即恰有 $a_i - 1$ 道题目比第 $i$ 道题目简单。
经验丰富的 cxy 早就悟出了一种科学地决定难度顺序的方法。首先， cxy 定义了难度递增子序列为序列 $a_{p_1}, a_{p_2}, \dots, a_{p_k}$ （$1 \le p_1 < p_2 < \dots < p_k \le n$） 满足 $a_{p_1} < a_{p_2} < \dots < a_{p_k}$ 。然后， cxy 决定了 $n$ 个整数 $f_1, \dots, f_n$，他希望找出一个难度顺序使得对于每个 $1 \le i \le n$ 均满足以 $a_i$ 结尾的难度递增子序列的最长长度恰好为 $f_i$。
但 cxy 日理万机，于是他找到了你，请你帮助 cxy 构造一个符合条件的 $a_1, \dots, a_n$ 吧！
输入格式：
第一行一个正整数 $n$。
接下来一行 $n$ 个数，其中第 $i$ 个数表示 $f_i$。（$1 \le f_i \le n$）
输出格式：
输出一行 $n$ 个数，表示 $a_1, \dots, a_n$。
题目保证至少存在一组解。如有多组解，输出任意一组均可。
数据范围：
$1 \le n \le 10^5$
若题目有解，则 $f_1 = 1$ ，且若 $f_i = k (k>1)$ ，则必存在 $1 \le j < i$ 使得 $f_j = k-1$ 。
因此构造序列使得 $f_i < f_j$ 时必有 $a_i < a_j$ ；当 $f_i = f_j$ 时，必有 $a_i > a_j$。（ $i < j$ ）
前者是显然的，后者解释一下。当 $f_i=f_j$ 时 $a_i$ 若小于 $a_j$ ，则 $f_j$ 应当为 $k+1$ 。因此这么构造是合法的。
具体地，把 $(f_i,a_i)$ 看作一个 pair<int,int> ，我们可以用计数排序来做，注意要正序做。
时间复杂度 $\mathcal{O}(n)$
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))
int n,m,a[N],b[N],buf[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
for(int i=1; i<=n; i++) { cin >> a[i]; ++buf[a[i]]; up(m, a[i]); }
for(int i=1; i<=m; i++) buf[i] += buf[i-1];
for(int i=1; i<=n; i++) cout << (buf[a[i]]--) << " \n"[i==n];
return 0;
}参考文献：
