汕头市队赛 SRM14 T2 最长上升子序列-白红宇

汕头市队赛 SRM14 T2 最长上升子序列

阅读量：6369 次

发布时间：2019-06-23

本文共 1866 字，大约阅读时间需要 6 分钟。

最长上升子序列

(tree.pas/c/cpp) 128MB 1s

有一个长度为n的序列a[i]，其中1到n的整数各自在a[i]中出现恰好一次。

现在已知另一个等长的序列f[i]，表示a[i]中以第i个位置结尾的最长上升子序列的长度，请还原出a[i]。

输入格式

第一行一个正整数n。

接下来一行n个数，其中第i个数表示f[i]。

输出格式

一行，n个整数，表示序列a[i]，如果答案不唯一，任意输出一种。

样例输入

1 2 3 2 4 4 3

样例输出

1 4 5 2 7 6 3

样例解释

以每个a[i]结尾的最长上升子序列分别为{1},{1,4},{1,4,5},{1,2},{1,4,5,7},{1,4,5,6},{1,2,3}

数据范围与约定

对于30%的数据，n<=10

对于另外40%的数据，n<=1000

对于所有数据，n<=100000

——————————————————————————————————————————

这道题当然可以按长度以及位置的前后进行一波排序解决问题（长度从小到大位置后（大）的在前）

这样复杂度是nlogn

所以我写的是拓扑排序（O（n））

我们枚举到一个数向值比他小1的数连线表示他比他大 1

同时向和他一样大的在他前一位的连线因为这样大小关系一样是确定的

然后就一波拓扑排序解决问题辣

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int M=2e5+7;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
    if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}bool f;int T,n,k,last[M],ans[M];int first[M],in[M],cnt;struct node{
    int to,next;}e[2*M];void ins(int a,int b){e[++cnt]=(node){b,first[a]}; first[a]=cnt;}std::queue
          
           q;int main(){    freopen("search.in","r",stdin);    freopen("search.out","w",stdout);    n=read();    for(int i=1;i<=n;i++){        k=read();        if(k>1&&!last[k-1]) f=true;        if(last[k]) ins(i,last[k]),in[last[k]]++;        if(last[k-1]) ins(last[k-1],i),in[i]++;        last[k]=i;    }    int h=0;    for(int i=1;i<=n;i++) if(!in[i]) q.push(i),ans[i]=++h;    while(!q.empty()){        int x=q.front(); q.pop();        for(int i=first[x];i;i=e[i].next){            int now=e[i].to;            if(ans[now]) continue;            in[now]--;            if(!in[now]) q.push(now),ans[now]=++h;        }    }    for(int i=1;i<=n;i++) printf("%d ",ans[i]); puts("");    return 0;}