博客

问题描述

解题思路

首先题意是给出n天的漫游信息以及n天的风险地区名单

求n天的风险人群

根据题意肯定要将漫游信息存储下来，用结构体数组比较合适

在判断该用户是否是风险人群时，需要判断[d1, d]区间内地点r是否是风险地区，所以需要把地点r的风险起始终止时间存储下来，可以采用map结合pair

并且开一个数组存储每天的风险人群答案，最后再排序去重输出

以下是我的数据结构，可参考，还有其他定义形式



然后就是读入每一天的漫游信息以及风险地区

当天就得出当天的风险人群

首先得到风险地区后，先更新每一个地区的风险时间段

在d天确认地点r为风险地区，那么目前r的风险终止时间一定会被更新成d + 6（未来7天内）

如果之前r不是风险地区或者d – 1天时已经不是风险地区，那么需要将r的风险起始时间更新为d，否则不更新

有了地区的风险时间段之后，就可以根据题目给出的条件判断这个用户是否是风险人群就可以了



对应的代码



最后将答案每一天依次输出，输出前进行编号的排序去重，存在重复的原因是因为漫游数据存在重复数据和多地访问数据

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <queue>

using namespace std;

struct node //存储漫游信息
{
    int day;
    int user;
    int address;
};

vector <node> alls[1010]; //存储每一天的有用的漫游信息
vector <int> res[1010]; //存储每一天的风险人群
unordered_map <int, pair <int, int>> A; //存储地点r的风险时间段
int n, r, m;

int main()
{
    scanf("%d", &n);

    for (int d = 0; d < n; d ++)
    {
        scanf("%d%d", &r, &m);
        for (int i = 0; i < r; i ++)
        {
            int x;
            scanf("%d", &x); //地点x在d天被确认为风险地区
            //如果x之前不是风险地区或者d-1天时x已经不是风险地区了
            if (A.count(x) == 0 || d - A[x].second > 1) A[x].first = d; //更新风险时间段的起点
            
            //更新风险时间的终点为 第 d + 6天
            A[x].second = d + 6;
        }

        for (int i = 0; i < m; i ++)
        {
            int d1, u, a;
            scanf("%d%d%d", &d1, &u, &a);
            //如果这天漫游信息中的地点不是风险地区或者当天已经不是风险地区或者是七天前的无效信息，则不需要保存
            if (A.count(a) == 0 || A[a].second < d || d1 < d - 6) continue;
            node t = {d1, u, a};
            alls[d].push_back(t); //存入当天的漫游信息
        }
        
        //处理[d-6, d]天中收到的有效漫游信息，得到风险人群
        for (int i = max(0, d - 6); i <= d; i ++)
        {
            for (int c = 0; c < alls[i].size(); c ++) //遍历第i天收到的漫游信息
            {
                int d1 = alls[i][c].day, u = alls[i][c].user, a = alls[i][c].address;
                //当前这个地区是风险地区
                //并且漫游信息是七天之内收到的漫游信息
                //并且[d1, d]这个时间段这个地区都是风险地区
                //则将这个人列入危险人群
                if (A.count(a) && d1 >= d - 6 && d1 >= A[a].first && d <= A[a].second) res[d].push_back(u);
            }
        }
    }

    for (int i = 0; i < n; i ++)
    {
        sort(res[i].begin(), res[i].end()); //排序
        //处理重复数据和多地点数据，可能一个人被列入多次
        res[i].erase(unique(res[i].begin(), res[i].end()), res[i].end());  //去重
        
        printf("%d", i);
        for (int j = 0; j < res[i].size(); j ++) printf(" %d", res[i][j]); //输出
        printf("\n");
    }
    return 0;
}