题解 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