题解 P7935 [COCI2007-2008#5] AVOGADRO

WsW_ · 2023-07-17 23:24:01 · 题解

思路：

将第一、二、三行的序列分别称为 a,b,c。
显然，当序列 a,b,c 中剩下的数字相同时，排序后三个序列相同，问题转化成要删除几列使得 a,b,c 中剩下的数字相同。
题目中保证序列 a 中包含 1\sim n 这 n 个整数，序列 b,c 中的数字在 1\sim n 范围内。显然，序列 b,c 中可能缺少某些数字，对于这些缺少的的数字，必须找到它在序列 a 的位置，并且把它在序列 a 中删除。
然而，必须整列删除，因此删除时还会删掉序列 b,c 中的数字，可能删了数字后序列 b,c 中又缺少某些数字了，我们再找到它在序列 a 的位置，并且把它在序列 a 中删除即可。
我选择用队列记录要删除哪些数字，每次弹出队首，并删除队首数字在序列 a 中对应的列，计数器加一。注意，若这个数字已经被删除过了，跳过即可！ 若这次操作导致序列 b,c 中缺少数字时，把缺少的数字加入队列。
当队列空时，说明 b,c 中已经不缺少数字了，停止循环，输出计数器中记录的次数。

代码：

//代码中i均指该数组中的下标 
#include<bits/stdc++.h>
using namespace std;
struct node{
    int a,b,c;
}s[100003];//在s中，下标代表列
queue<int> del;
int t[100003];//记录数字i在哪一列 
int cntb[100003],cntc[100003];//记录b,c中有几个数字i 
int ans;
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i].a);
        t[s[i].a]=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i].b);
        cntb[s[i].b]++;//在计数器中增加数字s[i].b的数量
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i].c);
        cntc[s[i].c]++;
    }
    for(int i=1;i<=n;i++)
        if(!cntb[i]||!cntc[i])del.push(i);//如果缺少数字i，将其加入队列
    while(!del.empty()){
        int x=del.front();//我们要删掉数字x 
        del.pop();
        if(t[x]==0)continue;//已经删过数字x了，跳过。 
        ans++;
        cntb[s[t[x]].b]--;
        cntc[s[t[x]].c]--;
        if(cntb[s[t[x]].b]==0)del.push(s[t[x]].b);
        if(cntc[s[t[x]].c]==0)del.push(s[t[x]].c);
        t[x]=0;//标记数字x已经被删了 
    }
    printf("%d",ans);
    return 0;
}