• 822 - Queue and A （UVA）

    题目链接如下：

    Online Judge

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

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

    AC代码如下：

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. // #define debug
    7.  
    8. struct topic{
    9.     int nbrOfRequest, elapsedTime, serviceTime, timeGap, lastRequest;
    10. };
    11. struct person{
    12.     int nbrOfTopics, idRank, recentJob;
    13.     int finishTime = 0;
    14.     std::vector<int> topicPriority;
    15. };
    16. int n, tid, nbrOfRequest, elapsedTime, serviceTime, timeGap, pid, nbrOfTopics, priority, lastRequest, finishTime, curr, kase = 0;
    17. std::unordered_map<int, topic> topicMap;
    18. std::unordered_map<int, person> personMap;
    19. std::unordered_map<int, int> currRequest;
    20. std::vector<int> pidVec;
    21. std::set<int> ttime;
    22.  
    23. bool cmp(const int &a, const int &b){
    24.     return personMap[a].recentJob != personMap[b].recentJob ? personMap[a].recentJob < personMap[b].recentJob : personMap[a].idRank < personMap[b].idRank;
    25. }
    26.  
    27. int main(){
    28.     #ifdef debug
    29.     freopen("0.txt", "r", stdin);
    30.     freopen("1.txt", "w", stdout);
    31.     #endif
    32.     while (scanf("%d", &n) == 1 && n){
    33.         lastRequest = 0;
    34.         finishTime = 0;
    35.         ttime.clear();
    36.         ttime.insert(0);
    37.         pidVec.clear();
    38.         topicMap.clear();
    39.         personMap.clear();
    40.         for (int i = 0; i < n; ++i){
    41.             scanf("%d %d %d %d %d", &tid, &nbrOfRequest, &elapsedTime, &serviceTime, &timeGap);
    42.             topicMap[tid].nbrOfRequest = nbrOfRequest;
    43.             topicMap[tid].elapsedTime = elapsedTime;
    44.             topicMap[tid].serviceTime = serviceTime;
    45.             topicMap[tid].timeGap = timeGap;
    46.             topicMap[tid].lastRequest = elapsedTime + (nbrOfRequest - 1) * timeGap;
    47.             lastRequest = std::max(lastRequest, topicMap[tid].lastRequest);
    48.             for (int j = 0; j < nbrOfRequest; ++j){
    49.                 ttime.insert(elapsedTime + j * timeGap);
    50.             }
    51.         }
    52.         scanf("%d", &n);
    53.         for (int i = 0; i < n; ++i){
    54.             scanf("%d %d", &pid, &nbrOfTopics);
    55.             pidVec.push_back(pid);
    56.             personMap[pid].nbrOfTopics = nbrOfTopics;
    57.             personMap[pid].idRank = i;
    58.             for (int j = 0; j < nbrOfTopics; ++j){
    59.                 scanf("%d", &priority);
    60.                 personMap[pid].topicPriority.push_back(priority);
    61.             }
    62.         }
    63.         sort(pidVec.begin(), pidVec.end(), cmp);
    64.         curr = 0;
    65.         while (1){
    66.             if (!ttime.count(curr)){
    67.                 ++curr;
    68.                 continue;
    69.             }
    70.             for (auto it = topicMap.begin(); it != topicMap.end(); ++it){
    71.                 if (curr >= it->second.elapsedTime && curr <= it->second.lastRequest && (curr - it->second.elapsedTime) % it->second.timeGap == 0){
    72.                     currRequest[it->first]++;
    73.                 }
    74.             }
    75.             if (currRequest.empty()){
    76.                 ++curr;
    77.                 continue;
    78.             }
    79.             for (int i = 0; i < pidVec.size(); ++i){
    80.                 if (personMap[pidVec[i]].finishTime <= curr){
    81.                     for (int j = 0; j < personMap[pidVec[i]].topicPriority.size(); ++j){
    82.                         int temp = personMap[pidVec[i]].topicPriority[j];
    83.                         if (currRequest.count(temp)){
    84.                             personMap[pidVec[i]].recentJob = curr;
    85.                             int ft = curr + topicMap[temp].serviceTime;
    86.                             personMap[pidVec[i]].finishTime = ft;
    87.                             ttime.insert(ft);
    88.                             finishTime = std::max(finishTime, ft);
    89.                             if (currRequest[temp] > 1){
    90.                                 currRequest[temp]--;
    91.                             } else {
    92.                                 currRequest.erase(temp);
    93.                             }
    94.                             break;
    95.                         }
    96.                     }
    97.                     if (currRequest.empty()){
    98.                         break;
    99.                     }
    100.                 }
    101.             }
    102.             if (currRequest.empty() && curr >= lastRequest){
    103.                 break;
    104.             }
    105.             ++curr;
    106.         }
    107.         printf("Scenario %d: All requests are serviced within %d minutes.\n", ++kase, finishTime);
    108.     }
    109.     #ifdef debug
    110.     fclose(stdin);
    111.     fclose(stdout);
    112.     #endif
    113.     return 0;
    114. }

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

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #define debug
    7.  
    8. struct topic{
    9.     int nbrOfRequest, elapsedTime, serviceTime, timeGap, lastRequest;
    10. };
    11. struct person{
    12.     int nbrOfTopics, idRank, recentJob;
    13.     int finishTime = 0;
    14.     std::vector<int> topicPriority;
    15. };
    16. int n, tid, nbrOfRequest, elapsedTime, serviceTime, timeGap, pid, nbrOfTopics, priority, lastRequest, finishTime, curr, kase = 0;
    17. std::unordered_map<int, topic> topicMap;
    18. std::unordered_map<int, person> personMap;
    19. std::unordered_map<int, int> currRequest;
    20. std::unordered_map<int, std::vector<int>> line;
    21. std::set<int> ttime;
    22.  
    23. bool cmp(const int &a, const int &b){
    24.     return personMap[a].recentJob != personMap[b].recentJob ? personMap[a].recentJob < personMap[b].recentJob : personMap[a].idRank < personMap[b].idRank;
    25. }
    26.  
    27. int main(){
    28.     #ifdef debug
    29.     freopen("0.txt", "r", stdin);
    30.     freopen("1.txt", "w", stdout);
    31.     #endif
    32.     while (scanf("%d", &n) == 1 && n){
    33.         lastRequest = 0;
    34.         finishTime = 0;
    35.         ttime.clear();
    36.         ttime.insert(0);
    37.         for (int i = 0; i < n; ++i){
    38.             scanf("%d %d %d %d %d", &tid, &nbrOfRequest, &elapsedTime, &serviceTime, &timeGap);
    39.             topicMap[tid].nbrOfRequest = nbrOfRequest;
    40.             topicMap[tid].elapsedTime = elapsedTime;
    41.             topicMap[tid].serviceTime = serviceTime;
    42.             topicMap[tid].timeGap = timeGap;
    43.             topicMap[tid].lastRequest = elapsedTime + (nbrOfRequest - 1) * timeGap;
    44.             lastRequest = std::max(lastRequest, topicMap[tid].lastRequest);
    45.             for (int j = 0; j < nbrOfRequest; ++j){
    46.                 ttime.insert(elapsedTime + j * timeGap);
    47.             }
    48.         }
    49.         scanf("%d", &n);
    50.         for (int i = 0; i < n; ++i){
    51.             scanf("%d %d", &pid, &nbrOfTopics);
    52.             personMap[pid].nbrOfTopics = nbrOfTopics;
    53.             personMap[pid].idRank = i;
    54.             for (int j = 0; j < nbrOfTopics; ++j){
    55.                 scanf("%d", &priority);
    56.                 personMap[pid].topicPriority.push_back(priority);
    57.             }
    58.         }
    59.         curr = 0;
    60.         while (1){
    61.             if (!ttime.count(curr)){
    62.                 ++curr;
    63.                 continue;
    64.             }
    65.             for (auto it = topicMap.begin(); it != topicMap.end(); ++it){
    66.                 if (curr >= it->second.elapsedTime && curr <= it->second.lastRequest && (curr - it->second.elapsedTime) % it->second.timeGap == 0){
    67.                     currRequest[it->first]++;
    68.                 }
    69.             }
    70.             while (!currRequest.empty()){
    71.                 line.clear();
    72.                 std::vector<int> empty;
    73.                 for (auto it = currRequest.begin(); it != currRequest.end(); ++it){
    74.                     line[it->first] = empty;
    75.                 }
    76.                 for (auto it = personMap.begin(); it != personMap.end(); ++it){
    77.                     if (it->second.finishTime <= curr){
    78.                         for (int i = 0; i < it->second.topicPriority.size(); ++i){
    79.                             if (currRequest.count(it->second.topicPriority[i])){
    80.                                 line[it->second.topicPriority[i]].push_back(it->first);
    81.                                 break;
    82.                             }
    83.                         }
    84.                     }
    85.                 }
    86.                 bool flag = true;
    87.                 for (auto it = line.begin(); it != line.end(); ++it){
    88.                     if (!it->second.empty()){
    89.                         flag = false;
    90.                         sort(it->second.begin(), it->second.end(), cmp);
    91.                         int temp = it->second[0];
    92.                         personMap[temp].recentJob = curr;
    93.                         personMap[temp].finishTime = curr + topicMap[it->first].serviceTime;
    94.                         ttime.insert(personMap[temp].finishTime);
    95.                         finishTime = std::max(finishTime, personMap[temp].finishTime);
    96.                         if (currRequest[it->first] > 1){
    97.                             currRequest[it->first]--;
    98.                         } else {
    99.                             currRequest.erase(it->first);
    100.                         }
    101.                     }
    102.                 }
    103.                 if (flag){
    104.                     break;
    105.                 }
    106.             }
    107.             if (currRequest.empty() && curr >= lastRequest){
    108.                 break;
    109.             }
    110.             ++curr;
    111.         }
    112.         printf("Scenario %d: All requests are serviced within %d minutes.\n", ++kase, finishTime);
    113.     }
    114.     #ifdef debug
    115.     fclose(stdin);
    116.     fclose(stdout);
    117.     #endif
    118.     return 0;
    119. }

  • 相关阅读:
    HTML期末学生大作业-拯救宠物网页作业html+css
    分布式文件系统HDFS(林子雨慕课课程)
    【SQLite】环境安装
    docker-compose安装nacos
    C++关键词探索：理解变量、函数参数、函数返回值以及类成员函数的修饰符
    Java绘图-第19章
    何为面向对象的编程思想
    Java中[Ljava.lang.Object；是什么?
    C# 自定义控件
    图解：Go Mutext
  • 原文地址：https://blog.csdn.net/linh2006/article/details/134282240