23ccpc（最长上升子序列题解）
你原本有一个 1 到 n 的排列但是不慎地你遗忘了它但是你记得以 第i个位置 结尾的最长上升子序 列的长度数组 an 现在希望你能够构造一个符合条件的排列 p 如果不存在符合上述条件的排列 p 则输出 −1。 这里定义以 第i位置 结尾的最长上升子序列的长度为符合以下条件的整数数组 id 中 k 的最大值。
1 ≤ id1 < id2 < id3 < · · · < idk = i pid1 < pid2 < pid3 < · · · < pidk 本题输入输出量比较大请选手注意。
Input 第一行一个整数 n (1 ≤ n ≤ 106) 第二行 n 个整数表示数组 an (1 ≤ ai ≤ n)其中 ai 表示以 i 结尾的最长上升子序列的长度。
Output 一行 n 个整数表示排列 p ,如果无解则输出 −1。
思路：
首先判断有没有符合的子序列，可以发现如果第a[i]为k,说明前边一定有子序列长度达到k-1,我们可以记录前i个a的最大值，如果a[i]>k+1,那么就没有这样的子序列。
如果有，有相同长度的子序列，如果j>i,那么p[j]<p[i]，然后根据子序列长度我们可以将1-n分成几份,然后根据序列长度，我让长的子序列拥有更大的值；
举个例子：
5
1 2 2 3 3
长度为3的子序列有两个，长度为2的子序列有两个，长度为1的子序列有1个。
我让3对应的位置上值为5，4（从大到小）
2对应的位置上值为3，2
1对应位置上值为1
整个序列为：
1 3 2 5 4
我们可以事先求出相同序列长度对应的最大值，然后从前往后遍历，输出一种序列在当前位置的值后，让值-1，接着往后遍历即可。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<unordered_map>
#include<map>
using namespace std;
typedef long long LL;
#define per(i,a,b) for(int i=a;i<=b;i++)
#define ber(i,a,b) for(int i=a;i>=b;i--)
const int N = 1e6 + 100;
int a[N],cn[N],ans[N],p[N];
int n;
int main()
{
cin >> n;
per(i, 1, n)
{
scanf("%d", &a[i]);
cn[a[i]]++;
}
int flag = 0, cnt = 0;
per(i, 1, n)
{
if (a[i] > cnt + 1)
{
flag = 1;
break;
}
else if (a[i] == cnt + 1)
cnt++;
}
if (flag)
{
cout << -1 << endl;
return 0;
}
cnt =n;
ber(i, n, 1)
{
if (cn[i])
{
p[i] = cnt;
cnt = cnt - cn[i];
}
}
per(i, 1, n)
{
ans[i] = p[a[i]];
p[a[i]]--;
}
for (int i = 1; i <= n-1; i++)
printf("%d ", ans[i]);
printf("%d\n", ans[n]);
return 0;
}