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.

## 代码

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

int a,b;
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;
}``````

上一篇 牛牛的Link Power II

2020-04-01 F2. Animal Observation (hard version)
F2. Animal Observation (hard version)time limit per test：3 seconds memory limit per test：512 megabytes inputstandard inp
2020-04-01
目录