822

822

题目链接如下：

Online Judge

这又是一道很恶心的模拟题。（然后看到网上说“又是一道简单的流程模拟题”，差点昏过去……）

开始的代码超时，想不出好的解决办法。后来看到uva 822_uva822 题意-CSDN博客 里一句“以人为循环主体来找工作，按照题目的要求(两个要求, 自己定义一个比较函数)把存储人的数组先进行排序, 对排序后的人依次找一个topic做就行了”，点醒了我。人只需要排序一次即可，每次按这个顺序让客服挑工作。

AC代码如下：

#include <cstdio>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
// #define debugstruct topic{int nbrOfRequest, elapsedTime, serviceTime, timeGap, lastRequest;
};
struct person{int nbrOfTopics, idRank, recentJob;int finishTime = 0;std::vector<int> topicPriority;
};
int n, tid, nbrOfRequest, elapsedTime, serviceTime, timeGap, pid, nbrOfTopics, priority, lastRequest, finishTime, curr, kase = 0;
std::unordered_map<int, topic> topicMap;
std::unordered_map<int, person> personMap;
std::unordered_map<int, int> currRequest;
std::vector<int> pidVec;
std::set<int> ttime;bool cmp(const int &a, const int &b){return personMap[a].recentJob != personMap[b].recentJob ? personMap[a].recentJob < personMap[b].recentJob : personMap[a].idRank < personMap[b].idRank;
}int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endifwhile (scanf("%d", &n) == 1 && n){lastRequest = 0;finishTime = 0;ttime.clear();ttime.insert(0);pidVec.clear();topicMap.clear();personMap.clear();for (int i = 0; i < n; ++i){scanf("%d %d %d %d %d", &tid, &nbrOfRequest, &elapsedTime, &serviceTime, &timeGap);topicMap[tid].nbrOfRequest = nbrOfRequest;topicMap[tid].elapsedTime = elapsedTime;topicMap[tid].serviceTime = serviceTime;topicMap[tid].timeGap = timeGap;topicMap[tid].lastRequest = elapsedTime + (nbrOfRequest - 1) * timeGap;lastRequest = std::max(lastRequest, topicMap[tid].lastRequest);for (int j = 0; j < nbrOfRequest; ++j){ttime.insert(elapsedTime + j * timeGap);}}scanf("%d", &n);for (int i = 0; i < n; ++i){scanf("%d %d", &pid, &nbrOfTopics);pidVec.push_back(pid);personMap[pid].nbrOfTopics = nbrOfTopics;personMap[pid].idRank = i;for (int j = 0; j < nbrOfTopics; ++j){scanf("%d", &priority);personMap[pid].topicPriority.push_back(priority);}}sort(pidVec.begin(), pidVec.end(), cmp);curr = 0;while (1){if (!ttime.count(curr)){++curr;continue;}for (auto it = topicMap.begin(); it != topicMap.end(); ++it){if (curr >= it->second.elapsedTime && curr <= it->second.lastRequest && (curr - it->second.elapsedTime) % it->second.timeGap == 0){currRequest[it->first]++;}}if (currRequest.empty()){++curr;continue;}for (int i = 0; i < pidVec.size(); ++i){if (personMap[pidVec[i]].finishTime <= curr){for (int j = 0; j < personMap[pidVec[i]].topicPriority.size(); ++j){int temp = personMap[pidVec[i]].topicPriority[j];if (currRequest.count(temp)){personMap[pidVec[i]].recentJob = curr;int ft = curr + topicMap[temp].serviceTime;personMap[pidVec[i]].finishTime = ft;ttime.insert(ft);finishTime = std::max(finishTime, ft);if (currRequest[temp] > 1){currRequest[temp]--;} else {currRequest.erase(temp);}break;}}if (currRequest.empty()){break;}}}if (currRequest.empty() && curr >= lastRequest){break;}++curr;}printf("Scenario %d: All requests are serviced within %d minutes.\n", ++kase, finishTime);}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}

一开始测试数据能过但是超时的代码如下：

#include <cstdio>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#define debugstruct topic{int nbrOfRequest, elapsedTime, serviceTime, timeGap, lastRequest;
};
struct person{int nbrOfTopics, idRank, recentJob;int finishTime = 0;std::vector<int> topicPriority;
};
int n, tid, nbrOfRequest, elapsedTime, serviceTime, timeGap, pid, nbrOfTopics, priority, lastRequest, finishTime, curr, kase = 0;
std::unordered_map<int, topic> topicMap;
std::unordered_map<int, person> personMap;
std::unordered_map<int, int> currRequest;
std::unordered_map<int, std::vector<int>> line;
std::set<int> ttime;bool cmp(const int &a, const int &b){return personMap[a].recentJob != personMap[b].recentJob ? personMap[a].recentJob < personMap[b].recentJob : personMap[a].idRank < personMap[b].idRank;
}int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endifwhile (scanf("%d", &n) == 1 && n){lastRequest = 0;finishTime = 0;ttime.clear();ttime.insert(0);for (int i = 0; i < n; ++i){scanf("%d %d %d %d %d", &tid, &nbrOfRequest, &elapsedTime, &serviceTime, &timeGap);topicMap[tid].nbrOfRequest = nbrOfRequest;topicMap[tid].elapsedTime = elapsedTime;topicMap[tid].serviceTime = serviceTime;topicMap[tid].timeGap = timeGap;topicMap[tid].lastRequest = elapsedTime + (nbrOfRequest - 1) * timeGap;lastRequest = std::max(lastRequest, topicMap[tid].lastRequest);for (int j = 0; j < nbrOfRequest; ++j){ttime.insert(elapsedTime + j * timeGap);}}scanf("%d", &n);for (int i = 0; i < n; ++i){scanf("%d %d", &pid, &nbrOfTopics);personMap[pid].nbrOfTopics = nbrOfTopics;personMap[pid].idRank = i;for (int j = 0; j < nbrOfTopics; ++j){scanf("%d", &priority);personMap[pid].topicPriority.push_back(priority);}}curr = 0;while (1){if (!ttime.count(curr)){++curr;continue;}for (auto it = topicMap.begin(); it != topicMap.end(); ++it){if (curr >= it->second.elapsedTime && curr <= it->second.lastRequest && (curr - it->second.elapsedTime) % it->second.timeGap == 0){currRequest[it->first]++;}}while (!currRequest.empty()){line.clear();std::vector<int> empty;for (auto it = currRequest.begin(); it != currRequest.end(); ++it){line[it->first] = empty;}for (auto it = personMap.begin(); it != personMap.end(); ++it){if (it->second.finishTime <= curr){for (int i = 0; i < it->second.topicPriority.size(); ++i){if (currRequest.count(it->second.topicPriority[i])){line[it->second.topicPriority[i]].push_back(it->first);break;}}}}bool flag = true;for (auto it = line.begin(); it != line.end(); ++it){if (!it->second.empty()){flag = false;sort(it->second.begin(), it->second.end(), cmp);int temp = it->second[0];personMap[temp].recentJob = curr;personMap[temp].finishTime = curr + topicMap[it->first].serviceTime;ttime.insert(personMap[temp].finishTime);finishTime = std::max(finishTime, personMap[temp].finishTime);if (currRequest[it->first] > 1){currRequest[it->first]--;} else {currRequest.erase(it->first);}}}if (flag){break;}}if (currRequest.empty() && curr >= lastRequest){break;}++curr;}printf("Scenario %d: All requests are serviced within %d minutes.\n", ++kase, finishTime);}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}