CSP-202209-3-防疫大数据
解题思路
一、数据结构定义
- 对于大模拟的题，合适的数据结构选择十分重要，正确的数据结构选择能够有效的提升解题效率
// 漫游消息结构体
struct RoamingData {
int date, user, region;
};
vector<RoamingData> roamingMessages[1010]; // 存储漫游消息
map<int, pair<int, int>> riskRegionDuration; // 每个地区的风险区持续时间
map<int, bool> isRiskRegion; // 每个地区是否曾被设为风险区
1.map简介
map是 C++ 标准库中的关联容器，实现了一个有序的键-值映射。每个元素都是一个包含键和值的键值对。以下是一些关键特性：
-
有序性：
map中的元素是按照键的大小进行排序的，默认是升序。 -
唯一键：每个键在
map中是唯一的，因此每个键只能对应一个值。如果插入重复键，新值会替代旧值。 -
查找效率：
map提供了高效的查找操作，其底层实现通常是红黑树，保证了对数时间复杂度的查找操作。
用法示例：
#include <map>
#include <iostream>
int main() {
// 创建一个map，键是字符串，值是整数
std::map<std::string, int> myMap;
// 插入键值对
myMap["apple"] = 5;
myMap["banana"] = 3;
myMap["orange"] = 7;
// 访问值
std::cout << "Number of apples: " << myMap["apple"] << std::endl;
// 遍历map
for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
2.pair简介
pair是 C++ 标准库中的一个模板类，用于表示一个有序的、固定大小的元组（tuple）包含两个元素。它提供了一种方便的方法来组合两个值，通常用于需要同时返回两个值或将两个值关联的场景。
-
成员变量
first：第一个元素。second：第二个元素。
-
等号重载：
pair& operator=(const pair& p);：允许将一个pair赋值给另一个。
-
使用示例：
#include <utility>
#include <iostream>
int main() {
// 创建一个pair，包含一个字符串和一个整数
std::pair<std::string, int> myPair = std::make_pair("apple", 5);
// 访问pair的成员
std::cout << "Fruit: " << myPair.first << ", Count: " << myPair.second << std::endl;
// 使用括号初始化列表创建pair
std::pair<int, double> anotherPair = {42, 3.14};
return 0;
}
二、风险区设置
- 函数
setRiskRegion的目的是将指定的地区标记为风险区，并更新该地区的风险区持续时间。下面是该函数的详细逻辑解释：
void setRiskRegion(int region, int date) {
// 如果地区不是风险区
if (!isRiskRegion[region]) {
// 将该地区标记为风险区，设置风险区持续时间为 [date, date + 6]
riskRegionDuration[region] = { date, date + 6 };
} else {
// 如果地区已经是风险区
if (date <= riskRegionDuration[region].second + 1) {
// 如果新日期与在原来风险区的有效日期内，直接延长有效期
riskRegionDuration[region].second = date + 6;
} else {
// 否则，重新设置风险区持续时间为 [date, date + 6]
riskRegionDuration[region] = { date, date + 6 };
}
}
// 标记该地区为风险区
isRiskRegion[region] = true;
}
这样，setRiskRegion 函数通过更新 riskRegionDuration 和 isRiskRegion 这两个数据结构，有效地管理每个地区的风险区状态和持续时间。
三、检查漫游消息是否满足条件
函数 check 的目的是检查给定的漫游消息是否满足一定条件，即该消息是否在风险区域内。
bool check(int messageDate, int user, int region, int currentDate) {
// 检查该地区是否是风险区，以及消息日期是否在指定范围内
if (isRiskRegion[region] &&
messageDate >= currentDate - 6 && messageDate <= currentDate &&
messageDate >= riskRegionDuration[region].first && currentDate <= riskRegionDuration[region].second)
return true;
return false;
}
-
检查风险区：首先，检查指定的地区是否被标记为风险区（通过
isRiskRegion的映射）。 -
检查消息日期范围：接着，检查消息的日期是否满足以下条件（否则必然是无效日期，因为风险地区的有效期已经结束）：
messageDate >= currentDate - 6：消息日期在当前日期的前 6 天之后。messageDate <= currentDate：消息日期在当前日期之前。
-
检查风险区域的日期范围：最后，检查消息日期是否在该地区的风险区域持续时间范围内，即：
messageDate >= riskRegionDuration[region].first：消息日期在风险区域开始日期之后。currentDate <= riskRegionDuration[region].second：当前日期在风险区域结束日期之前。
如果所有条件都满足，则返回 true，表示该漫游消息在风险区域内；否则，返回 false。
完整代码
- 注意：只需遍历过去七天的漫游消息而不需要遍历全部消息，否则会时间超限。
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
// 漫游消息结构体
struct RoamingData {
int date, user, region;
};
vector<RoamingData> roamingMessages[1010]; // 存储漫游消息
map<int, pair<int, int>> riskRegionDuration; // 每个地区的风险区持续时间
map<int, bool> isRiskRegion; // 每个地区是否曾被设为风险区
// 设置地区为风险区
void setRiskRegion(int region, int date) {
if (!isRiskRegion[region])
riskRegionDuration[region] = { date, date + 6 };
else {
if (date <= riskRegionDuration[region].second + 1)
riskRegionDuration[region].second = date + 6; // 可以连起来
else
riskRegionDuration[region] = { date, date + 6 };
}
isRiskRegion[region] = true;
}
// 检查漫游消息是否满足条件
bool check(int messageDate, int user, int region, int currentDate) {
if (isRiskRegion[region] &&
messageDate >= currentDate - 6 && messageDate <= currentDate &&
messageDate >= riskRegionDuration[region].first && currentDate <= riskRegionDuration[region].second)
return true;
return false;
}
int main() {
int days;
cin >> days;
for (int currentDay = 0; currentDay < days; currentDay++) { // currentDay表示当前日期
int riskRegions, roamingMessagesCount;
cin >> riskRegions >> roamingMessagesCount;
for (int i = 1; i <= riskRegions; i++) { // 读入风险区并更新
int region;
cin >> region;
setRiskRegion(region, currentDay);
}
for (int i = 1; i <= roamingMessagesCount; i++) { // 读入漫游消息并存入
int date, user, region;
cin >> date >> user >> region;
if (date <= currentDay)
roamingMessages[currentDay].push_back({ date, user, region });
}
set<int> riskUserList; // 当天的风险名单
// 遍历过去七天的漫游消息
for (int i = (currentDay - 6 >= 0 ? currentDay - 6 : 0); i <= currentDay; i++) {
// 对于每一天的漫游消息列表
for (int j = 0; j < roamingMessages[i].size(); j++) {
// 检查漫游消息是否满足条件
if (check(roamingMessages[i][j].date, roamingMessages[i][j].user, roamingMessages[i][j].region, currentDay))
// 如果满足条件，将用户添加到风险用户列表
riskUserList.insert(roamingMessages[i][j].user);
}
}
cout << currentDay << " ";
for (const auto& ii : riskUserList) {
cout << ii << " ";
}
cout << endl;
}
return 0;
}
