K题:(搞不懂拓扑排序的超小白讲解)
总体思路为利用已知b[i]推出b[i-1]信息,将1-n每个数填充至ans数组构造答案.
直接进行代码讲解:
首先读入数据,我们用一个book数组来记录当前位置是否有约束,显然当下标小于需要长度或者两者大于n时输出-1

#include<bits/stdc++.h>
using namespace std;
int b[N],book[N],ans[N];
int main()
{
    int n,k,f=1;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        int t,w;
        cin>>t>>w;
        b[t]=w;
        book[t]=1;
        if(w>t||t>n||w>n){f=0;}
    }
    if(f==0){puts("-1");return 0;}
}

根据输入的b[i]来获取一些有需要的信息,用样例2来说明
5 2
2 2
5 4
由小到大历遍
b[2]=2我们显然能知道b[1]=b[2]-1 (b[i]最小值为1)且ans[2]>=ans[1] (区间1-2单调不减)
那么由b[5]=4,同理可得b[4]=3,b[3]=2,b[2]已经被约束过停止ans[5]>=ans[4]>=ans[3] (区间3-5单调不减);

for(int i=1;i<=n;i++)
    {
        if(book[i])
        {
            for(int j=i-1;j>=1&&!book[j];j--)
            {
                b[j]=max(b[j+1]-1,1);
                book[j]=1;
            }
        }
    }
for(int i=1;i<=n;i++)//对于一次历遍未有约束项赋值,后续详细讲.
    { 
        if(book[i]==0)b[i]=b[i-1];
    }

下面我们考虑的问题是如何根据已知信息将1-n填入数组
我们有自然数集合S{1...n}
操作优先级如下,
1.当b[i]!=b[j]的优先填充较小的数ans[i]=min(S)(b[i]<b[j])
2.当b[i]=b[j]时将最小的数填充到数组下标较大ans[i]=min(S)(i>j)
同样用上述样例来说明我们已知b[1]=1,b[2]=2,b[3]=2,b[4]=3,b[5]=4;
根据操作步骤ans[1]=1 ans[3]=2 ans[2]=3 ans[4]=4 ans[5]=5;
最终答案为 1 3 2 4 5 符合题意
操作1是因为b中一定存在b[i]=1,由于b[i]<=i我们一定有b[1]=1,i!=1时保证满足ans[i]<ansj
对于操作2其实很容易理解当b[j]=b[i]+1我们只需要满足在区间[i,j]单调递减,所以我们只要从下标大的开始赋值即可,且由于每个自然数只有一个,如果将小的数放在前面就会压在栈底,使得后续答案不满足,这里说明对于一次历遍未有约束项赋值也是为了不影响后续答案,方便将较大的数直接弹出,那么根据操作1.2一定存在一种序列可以将S不重不漏填入数组
操作2证明如下
对于b[i]=b[j]若ans[i]<ans[j] b[i]=x 由于j>i b[j]>=x+1 显然与b[i]=b[j]矛盾.
那么根据操作1.2一定存在一种序列可以将S不重不漏填入数组,所以我们只需要做一个结构体排序即可

struct p
{
    int num,w;//下标和b[i];
}po[N];
bool cmp(struct p a,struct p b)
{
    if(a.w!=b.w)return a.w<b.w;
    else return a.num>b.num;
}
for(int i=1;i<=n;i++)
    { 
        if(book[i]==0)b[i]=b[i-1];

        po[i].num=i;
        po[i].w=b[i];
    }
sort(po+1,po+1+n,cmp);
for(int i=1;i<=n;i++)
    {
        ans[po[i].num]=i;
    }
     for(int i=1;i<=n;i++)
    {
       cout<<ans[i]<<" ";
    }

完整AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
struct p
{
    int num,w;
}po[N];
bool cmp(struct p a,struct p b)
{
    if(a.w!=b.w)return a.w<b.w;
    else return a.num>b.num;
}
int b[N],book[N],ans[N];
int main()
{
    int n,k,f=1;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        int t,w;
        cin>>t>>w;
        b[t]=w;
        book[t]=1;
        if(w>t||t>n||w>n){f=0;}
    }
    if(f==0){puts("-1");return 0;}
    for(int i=1;i<=n;i++)
    {
        if(book[i])
        {
            for(int j=i-1;j>=1&&!book[j];j--)
            {
                b[j]=max(b[j+1]-1,1);
                book[j]=1;
            }
        }
    }
    for(int i=1;i<=n;i++)
    { 
        if(book[i]==0)b[i]=b[i-1];

        po[i].num=i;
        po[i].w=b[i];
    }
    sort(po+1,po+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        ans[po[i].num]=i;
    }
     for(int i=1;i<=n;i++)
    {
       cout<<ans[i]<<" ";
    }
}.