1003. Covid (思维 / 小根堆)(2020年百度之星*程序设计大赛-初赛二)

传送门

思路：

• 比赛的时候想到用并查集，但发现变量很多不知道怎么实现，一直写不出。

• 官方题解：
  (小根堆的代码后期若写出再来补充！)

• 看了wyh的代码才知道其实这个题很简单。直接用个三维数组，第一维记录时间，第二维记录地点，第三维当然就是记录人员编号了。

• 然后以<时间，地点>为索引来处理，具体细节见代码。(比赛时我就傻傻的以人头为索引来处理，结果后面发现这样处理会不完全。)

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

inline void read(int &x){
    char t=getchar();
    while(!isdigit(t)) t=getchar();
    for(x=t^48,t=getchar();isdigit(t);t=getchar()) x=x*10+(t^48);
}

int T, n, vis[N];
vector<int> ans, mp[105][15];


int main()
{
    read(T);
    while(T --){
        read(n);
        //初始化数组
        for(int i=1;i<=100;i++)
            for(int j=1;j<=10;j++)
                mp[i][j].clear();
        //将对应的人员编号分配到相应的<时间，地点>元组里
        for(int i = 1; i <= n; i ++){
            int len; read(len);
            for(int j = 1; j <= len; j ++){
                int t, p; read(t); read(p);
                mp[t][p].push_back(i);
            }
        }
        vis[1] = 1; //先将1号人员标记已被感染
        for(int i = 1; i <= 100; i ++){
            for(int j = 1; j <= 10; j ++){
                int ok = 0;
                for(auto it : mp[i][j])
                    if(vis[it]){ok = 1; break;} //若发现该<时间，地点>有一人已被感染。
                if(ok) for(auto it : mp[i][j]) vis[it] = 1; //那么标记该<时间，地点>的人员都已被感染
            }
        }
        ans.clear();
        for(int i = 1; i <= n; i ++) //开始在所有人员中锁定被感染人员，并释放该位置的标号vis[i]
            if(vis[i]){ans.push_back(i); vis[i] = 0;}
        for(int i = 0; i < ans.size()-1; i ++) printf("%d ", ans[i]);
        printf("%d\n", ans.back());
    }

    return 0;
}