題目鏈接：點擊查看

題目大意：題目給出 n - 1 個大小關系，分別代表一個長度為 n 的數(shù)列各個位置的相對大小，現(xiàn)在需要我們用兩個符合相對大小關系的 1 ~?n 的一個排列，且該排列的最長不下降子序列分別最小和最大

題目分析：讀完題后不難想到，如果我們想讓最長不下降子序列最長的話，那么整個序列必然是呈整體上升的趨勢，最小的話相應的是整個序列呈下降趨勢，因為多了相對大小這個約束，我們可以使得符號相同的連續(xù)序列分成不同的區(qū)塊，每個區(qū)塊只要保持整體上升的趨勢就行，換句話說，必須保證后一個區(qū)塊的最小值比前一個區(qū)塊的最大值還要大才行，這樣我們善于運用一下reverse函數(shù)就可以輕松實現(xiàn)了，比賽的時候因為B題讀錯題了慌了神，導致這個簡單題沒有出，坐等掉分

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;char s[N];int ans[N];int main() { //#ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); //#endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n;scanf("%d%s",&n,s+1);for(int i=1;i<=n;i++)ans[i]=n-i+1;for(int i=1;i<=n-1;)//整體下降 {int j=i;while(s[j]=='<')j++;reverse(ans+i,ans+j+1);i=j+1;}for(int i=1;i<=n;i++)printf("%d ",ans[i]);printf("\n");for(int i=1;i<=n;i++)ans[i]=i;for(int i=1;i<=n-1;)//整體上升 {int j=i;while(s[j]=='>')j++;reverse(ans+i,ans+j+1);i=j+1;}for(int i=1;i<=n;i++)printf("%d ",ans[i]);printf("\n");}return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1304D Shortest and Longest LIS(构造+贪心)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。