1073B Vasya and Books-蒲公英云

1073B Vasya and Books

梦里梦外; 2022-05-14 15:16 292阅读 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]])