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;
}