题解 CF1304D 【Shortest and Longest LIS】

· · 题解

这道题构造方法感觉很多，我就说一说自己的吧。据我所知我的写法应该算是很简洁的。

题目大意

有一个 1 到 n 的排列，你知道所有相邻两个位置的大小关系，你需要构造出两个排列，满足第一个排列的 LIS 尽可能短，第二个排列的 LIS 尽可能长。

数据范围

1\le n\le 2\times 10^5

解题过程

首先考虑构造最短的 LIS。

容易发现此时答案的下界是连续相邻 '<' 的长度的最大值。现在我们尝试打到这个最大值。

我们可以这么构造：首先让这个排列等于 n,n-1,n-2,\ldots,1，然后对于一段连续的 '<'，我们直接把对应的位置翻转。

这样对于任意两个位置 i<j，除非这两个位置位于一段连续的 '<' 对应的区间之内，否则一定满足 a_i>a_j。可以发现这样构造出的 LIS 一定是最短的。

然后我们考虑构造最长的 LIS。

有了上面的思考过程，这次我们只需要让这个排列初始等于 1,2,3,\ldots,n，然后翻转所有连续的 '>' 对应的区间。这样对于任意两个位置 i<j，除非这两个位置位于一段连续的 '>' 对应的区间之内，否则一定满足 a_i<a_j。因此这样构造出的 LIS 一定是最长的。

时间复杂度 O(n)。

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int t,n,p[200005];
char s[200005];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%s",&n,s+1);
        for(int i=1;i<=n;i++)p[i]=n-i+1;
        for(int i=1;i<n;)
        {
            int j=i;
            while(s[j]=='<')j++;
            reverse(p+i,p+j+1);
            i=j+1;
        }
        for(int i=1;i<=n;i++)printf("%d ",p[i]);
        printf("\n");
        for(int i=1;i<=n;i++)p[i]=i;
        for(int i=1;i<n;)
        {
            int j=i;
            while(s[j]=='>')j++;
            reverse(p+i,p+j+1);
            i=j+1;
        }
        for(int i=1;i<=n;i++)printf("%d ",p[i]);
        printf("\n");
    }
    return 0;
}