P8889 [入门赛 #7] 狠狠地切割 (Hard Version) 题解

liwenxi114514 · 2024-07-08 13:59:41 · 个人记录

题意

有两个数组 a 和 b，在 a 数组中找到所有存在于 b 数组中的数，将它们删除并将 a 数组分成几个部分。问最后数组 a 被分成了几个部分。

思路

观察到数组中的数字很大，于是想到用 map 来存储，但是 map 太慢了，所以用 c++14 中的 unordered_map，即无序键值对，它的用法与 map 一样，但一般的插入和删除都是 O(1) 的。所以我们可以存储 a 数组中的每一个数的多个位置，最后统一分段即可。详见代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[500005],b[500005];
unordered_map<int,vector<int> > v;//由于一个数可能会出现多次，所以要用vector
bool vis[500005];
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v[a[i]].push_back(i);//存储数字的位置
    } 
    for(int i=1;i<=m;i++){
        cin>>b[i];
        for(int j=0;j<v[b[i]].size();j++){
            vis[v[b[i]][j]]=1;//相当于分界点
        }
    }
    int sum=0,ans=0;
    for(int i=1;i<=n;i++){
        if(vis[i]==1){//如果遍历到了分界点
            if(sum!=0){//如果不是空串
                ans++;//段数加一
                sum=0;
            }
        }else{
            sum++;//累加长度
        }
    }
    if(sum!=0){//记得在最后也要判断一次
        ans++;
        sum=0;
    }
    cout<<ans;
    return 0;//完结撒花！！！
}