题解 CF1073B 【Vasya and Books】
粗略看了一下 貌似没人和我的解法相同
那就来写一发题解吧
在读入的时候 我们用另一个数组lead[i]来存编号为i的书在读入的数组book[]的下标
这样我们在检测读入的书是否被取出时就不用遍历一遍book[]
弹出书本的时候,我们首先看一下这个书本是否被取出
如果是就直接输出0
否则就开始弹出书本
我们用一个变量now = 0记录当前弹出了几个书本,用一个数组vis[i]记录第i本书是否被弹出
在弹出之前,用一个变量orin记录一下还没更新的now
接着在每次弹出的时候更新vis[++now]为真,直到遇到当前要弹出的书本编号
最后orin - now即为答案
代码实现:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <stack>
using std::cin;
using std::cout;
using std::endl;
using std::string;
const int MAXN = 2e5 + 10;
int n;
int book[MAXN];
int lead[MAXN];
bool vis[MAXN];
int now = 0;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", book + i);
lead[book[i]] = i;
// 让lead[]作为book[]的索引,查找的时候快一些
}
for (int i = 1; i <= n; ++i) {
int o;
scanf("%d", &o);
if (vis[lead[o]]) printf("0 ");
// 被弹过了,输出0
else {
int orin = now;
while (book[++now] != o) {
vis[now] = true;
// 循环更新vis(弹出书本)
}
vis[now] = true;
printf("%d ", now - orin);
}
}
return 0;
}
总感觉自己的代码能被 Hack