1073B Vasya and Books

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

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

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

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

c++:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[200010],val;
  4. int b[200010];
  5. int main()
  6. {
  7. int n;
  8. scanf("%d",&n);
  9. for(int i=1;i<=n;i++)
  10. {
  11. scanf("%d",&val);
  12. a[val]=i;
  13. }
  14. int maxx=0;
  15. for(int i=1;i<=n;i++)
  16. {
  17. scanf("%d",&b[i]);
  18. if(a[b[i]]>maxx)
  19. {
  20. printf("%d ",a[b[i]]-maxx);
  21. maxx=a[b[i]];
  22. }
  23. else printf("0 ");
  24. }
  25. printf("\n");
  26. return 0;
  27. }

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

超时代码:

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

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

  1. n=int(input())
  2. a=list(map(int,input().split()))
  3. b=list(map(int,input().split()))
  4. cnt=[0]*(n+1);
  5. maxx=0
  6. for i in range(n):
  7. cnt[a[i]]=i+1
  8. for i in range(n):
  9. print(max(0,cnt[b[i]]-maxx),end=" ")
  10. maxx=max(maxx,cnt[b[i]])

发表评论

表情:
评论列表 (有 0 条评论,293人围观)

还没有评论,来说两句吧...

相关阅读

    相关 1073B Vasya and Books

      题意:有n本书,按照a那种顺序叠在一起,按照b那种顺序取书,如果取的这本书上面还有书,那就一起拿走装进包里, 输出按照b的顺序每次能拿几本书。 题解:模拟 先把最开始