题解 CF1073B 【Vasya and Books】

粗略看了一下 貌似没人和我的解法相同 那就来写一发题解吧 在读入的时候 我们用另一个数组`lead[i]`来存编号为`i`的书在**读入的数组`book[]`**的下标 这样我们在检测读入的书是否被取出时就不用遍历一遍`book[]` --- 弹出书本的时候，我们首先看一下这个书本是否被取出 如果是就直接输出`0 ` 否则就开始弹出书本 --- 我们用一个变量`now = 0`记录当前弹出了几个书本，用一个数组`vis[i]`记录第`i`本书是否被弹出 在弹出之前，用一个变量`orin`记录一下**还没更新**的`now` 接着在每次弹出的时候更新`vis[++now]`为真，直到遇到当前要弹出的书本编号 最后`orin - now`即为答案 --- 代码实现： ```cpp #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~~