专栏首页一Wa哇一天D. Shortest and Longest LIS

D. Shortest and Longest LIS

题目链接:D. Shortest and Longest LIS

time limit per test3 seconds memory limit per test256 megabytes inputstandard input outputstandard output

Gildong recently learned how to find the longest increasing subsequence (LIS) in O(nlogn) time for a sequence of length n. He wants to test himself if he can implement it correctly, but he couldn’t find any online judges that would do it (even though there are actually many of them). So instead he’s going to make a quiz for you about making permutations of n distinct integers between 1 and n, inclusive, to test his code with your output.

The quiz is as follows.

Gildong provides a string of length n−1, consisting of characters ‘<’ and ‘>’ only. The i-th (1-indexed) character is the comparison result between the i-th element and the i+1-st element of the sequence. If the i-th character of the string is ‘<’, then the i-th element of the sequence is less than the i+1-st element. If the i-th character of the string is ‘>’, then the i-th element of the sequence is greater than the i+1-st element.

He wants you to find two possible sequences (not necessarily distinct) consisting of n distinct integers between 1 and n, inclusive, each satisfying the comparison results, where the length of the LIS of the first sequence is minimum possible, and the length of the LIS of the second sequence is maximum possible.

Input Each test contains one or more test cases. The first line contains the number of test cases t (1≤t≤104).

Each test case contains exactly one line, consisting of an integer and a string consisting of characters ‘<’ and ‘>’ only. The integer is n (2≤n≤2⋅105), the length of the permutation you need to find. The string is the comparison results explained in the description. The length of the string is n−1.

It is guaranteed that the sum of all n in all test cases doesn’t exceed 2⋅10^5^.

Output For each test case, print two lines with n integers each. The first line is the sequence with the minimum length of the LIS, and the second line is the sequence with the maximum length of the LIS. If there are multiple answers, print any one of them. Each sequence should contain all integers between 1 and n, inclusive, and should satisfy the comparison results.

It can be shown that at least one answer always exists.

Example

input

3
3 <<
7 >><>><
5 >>><

output

1 2 3
1 2 3
5 4 3 7 2 1 6
4 3 1 7 5 2 6
4 3 2 1 5
5 4 2 1 3

Note In the first case, 1 2 3 is the only possible answer. In the second case, the shortest length of the LIS is 2, and the longest length of the LIS is 3. In the example of the maximum LIS sequence, 4 ‘3’ 1 7 ‘5’ 2 ‘6’ can be one of the possible LIS.

题目大意

先给你一个数字 t 便是有T 组,然后给了一个N 表示有N个数,后面跟着N-1个字符,表示一个大小关系,然后让你输出个一构造出的最短和最长的上升子序列。

解题思路

看了大佬们的博客后才知道,远了这个题这么妙,如果是最长的我肯定想尽可能的让所有的 > 可以联合到一起,对于最短的我们一个策略就是让 > 尽可能的不能相连,那么的话我们可以采取一个分块的策略,分别根据 < 和 > 进行分块,对于最短的我们肯定是我们按照 > 将这个序列分成若干块,让大的数子尽可能的放到前面,对于最长的我们按照 < 进行换分让前面的数字尽可能的小,让我们看下代码吧

代码

#include<bits/stdc++.h>
using namespace std;

int a[200010],b[200100];
string s;
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n>>s;
        int l=0,num=n;//先处理最短的 
        for(int i=0;i<n;i++)
        {
            if(i==n-1||s[i]=='>')//当走倒最后一个,或者遇到 > 进行划分 
            {                    //将其分成一块进行赋值 
                for(int j=i;j>=l;j--)//因为是最短,所以需要让前面的数字尽可能的大 
                a[j]=num--;// 因为是用 > 进行分割的所以这一块里面都是小于号   
                l=i+1;       //从后向前开始复制,之后移动左边界    
            }
        }
        l=0,num=1;
        //处理最长的 
        for(int i=0;i<n;i++)
        {
            if(i==n-1||s[i]=='<')//这是按照 < 进行划分 
            {
                for(int j=i;j>=l;j--) //将前面的值尽可能的小 
                b[j]=num++;//因为这个区间内都是 > 号所以还是才有从后向前走 
                l=i+1;
            }
        }
        for(int i=0;i<n;i++) cout<<a[i]<<" ";
        cout<<"\n";
        for(int i=0;i<n;i++) cout<<b[i]<<" ";
        cout<<"\n";
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C. NEKO's Maze Game

    time limit per test:1.5 seconds memory limit per test:256 megabytes inputstandar...

    某些人
  • 2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)-G.Projection

    Everybody knows that you are a TensorFlow fan. Therefore, you’ve been challenged...

    某些人
  • CF-1121D-D. Make The Fence Great Again

    time limit per test:2 seconds memory limit per test:256 megabytes inputstandard ...

    某些人
  • Procrustean回归网络:从2D注释中学习非刚性对象的3D结构

    中文摘要:我们提出了一种用于训练神经网络的新颖框架,该框架能够在只有2D注释作为基本事实可用时学习非刚性对象的3D信息。近年来,已经有一些方法将非刚性运动结构的...

    用户7454122
  • 非均匀页岩气在超致密约束下的非平衡输运(CS.CE)

    在许多工程应用中都遇到过表面高度封闭的非均匀致密气体的非平衡输运问题。例如,在页岩气生产过程中,甲烷是在高压下从超致密孔隙中提取出来的,因此气体是不均匀且致密的...

    用户7236395
  • 3道线段树题

    A city's skyline is the outer contour of the silhouette formed by all the buildi...

    王脸小
  • FAST Algorithm for Corner Detection

    We saw several feature detectors and many of them are really good. But when look...

    bear_fish
  • Partitioning in SQL Server 2008

    Why don’t you partition your table if you have millions of rows and get complain...

    javascript.shop
  • R语言犯罪率回归模型报告Regression model on crimerate report

    From the plot,we can see murder has negative relationship with frost and life ex...

    拓端
  • 时间序列预测与递归神经网络在Keras的应用基于Python

    编辑整理 编辑部:西西 原文作者 Jason Brownlee 问题描述 问题为:国际客运量预测。该数据范围从 1949 年 1 月至 1960 年 12 月。...

    量化投资与机器学习微信公众号

扫码关注云+社区

领取腾讯云代金券