题解 | #Stack#

K题题解

法1： 构造拓扑关系

思路：先假设 我们要求的序列 a 为: 1、2、3、...... 、n
然后对序列 a 进行题目描述中的单调栈操作， 构造出满足 所给b[i] 的拓扑关系
拓扑关系：在这里 指位置间的拓扑关系 ，比如 pos1 指向 pos2 , 代表 a[pos1] 需大于 a[pos2]

Code 如下

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 1e6+10;

PII p[N];
int a[N],b[N];        //如题
int to[N];           // to[i]：i指向to[i]，拓扑关系
int in[N];          // 入度
int stk[N],q[N];   // 模拟栈、队列
int n,k;

bool check(){  
     for(int i=0;i<k;i++){
            int pos=p[i].first,val=p[i].second;
            int pp=p[i+1].first,vv=p[i+1].second;
            if(pos<val) return true;
            if(i==k-1) break;
           if(val+pp-pos<vv) return true;
        }
     return false;
}

void topsort(){    //求拓扑序
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++) if(!in[i])  q[++tt]=i;

    while(hh<=tt){  // 模拟队列  ps：个人偏爱于使用模拟队列求拓扑序，非必须 
        int t=q[hh++];
        in[to[t]]--;
        if(in[to[t]]==0) q[++tt]=to[t];
    }

    int t=n;
    for(int i=0;i<=tt;i++){
       int pos=q[i];
       a[pos]=t--; 
    }

    // 输出序列 a
    for(int i=1;i<=n;i++) cout<<a[i]<<" \n"[i==n];
}

void solve(){     
    int h=0;
    for(int i=1;i<=n;i++){
        if(b[i]){      //b[i]确定，需满足b[i]
            bool u=false;
            while(h>b[i]-1) h--,u=true;     //为了保证入栈后，栈中有b[i]个元素
            if(u) to[stk[h+1]]=i;          // 拓扑关系：a[stk[h+1]] > a[i]
        } 
        // b[i]不确定，尽情入栈。不会与b[i]产生冲突
        stk[++h]=i;
        to[i]=stk[h-1];  // 拓扑关系：a[i] > a[stk[h-1]]
    }
    for(int i=1;i<=n;i++) in[to[i]]++;
    topsort();
}

int main(){
    cin>>n>>k;
    for(int i=0;i<k;i++){
        int pos,val;
        cin>>pos>>val;
        p[i]={pos,val};
        b[pos]=val;  
    }

    if(check())  puts("-1");    
    else  solve();

    return 0;
}

法2 模拟

思路 参考 ：https://blog.nowcoder.net/n/1a8897ea58004f15a93d0ee7009ac99a

Code 如下

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 1e6+10;

PII p[N];
bool st[N];
int a[N];
int b[N];
int n,k;

bool cmp(PII x,PII y){
    int pos=x.first,val=x.second;
    int pp=y.first,vv=y.second;
    if(val==vv) return pos>pp;
    return val<vv;
}

bool check(){
     for(int i=0;i<k;i++){
            int pos=p[i].first,val=p[i].second;
            int pp=p[i+1].first,vv=p[i+1].second;
            if(pos<val) return true;
            if(i==k-1) break;
           if(val+pp-pos<vv) return true;
        }
     return false;
}

void solve(){
     for(int i=0;i<k;i++){
         int pos=p[i].first,val=p[i].second;
         int t=1;
         for(int j=pos-1;j>=1&&!st[j];j--)  b[j]=max(1,val-t),t++;
     }

     for(int i=1;i<=n;i++) if(!b[i]) b[i]=b[i-1];  // 尾部要特殊处理

     memset(p,0,sizeof p);   for(int i=1;i<=n;i++)  p[i]={i,b[i]};

     sort(p+1,p+n+1,cmp);
     for(int i=1;i<=n;i++){
         int pos=p[i].first;
         a[pos]=i;
     }
     for(int i=1;i<=n;i++) cout<<a[i]<<" \n"[i==n];
}

int main(){
    cin>>n>>k;
    for(int i=0;i<k;i++){
        int pos,val;
        cin>>pos>>val;
        p[i]={pos,val};
        st[pos]=true;
        b[pos]=val;   
    }
    if(check())  puts("-1");
    else  solve();

    return 0;
}