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;
}参考文献：
