1073B Vasya and Books

梦里梦外; 2022-05-14 15:16 190阅读 0赞

题意：有n本书，按照a那种顺序叠在一起，按照b那种顺序取书，如果取的这本书上面还有书，那就一起拿走装进包里，

输出按照b的顺序每次能拿几本书。

题解：模拟 先把最开始书籍的顺序（下标）记录下来，然后按照b的顺序遍历a中的下标，并且记录上一次拿书的下标，最开始为0，如果当前要拿的数下标在原始顺序中上面有书，就拿下标减上一次拿的下标，如果小于就说明没有书可拿。

c++：

#include<bits/stdc++.h>
    using namespace std;
    int a[200010],val;
    int b[200010];
    int main()
    {
        int n;
        scanf("%d",&n);
       for(int i=1;i<=n;i++)
       {
           scanf("%d",&val);
           a[val]=i;
       }
       int maxx=0;
       for(int i=1;i<=n;i++)
       {
           scanf("%d",&b[i]);
           if(a[b[i]]>maxx)
           {
               printf("%d ",a[b[i]]-maxx);
               maxx=a[b[i]];
           }
           else printf("0 ");
       }
       printf("\n");
        return 0;
    }

python：python最开始没记录下标，直接调用下标会超时，应该是底层源代码中有循序遍历，所以超时了...

超时代码：

n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    maxx=0;
    for i in b:
        if a.index(i)+1>maxx:
            print(a.index(i)+1-maxx,end=" ")
            maxx=a.index(i)+1

ac代码：还是像c那样先记录原来顺序

n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    cnt=[0]*(n+1);
    maxx=0
    for i in range(n):
        cnt[a[i]]=i+1
    for i in range(n):
        print(max(0,cnt[b[i]]-maxx),end=" ")
        maxx=max(maxx,cnt[b[i]])