问题描述
p12108原题链接:UVaOJ 12108 - Extraordinarily Tired Students
相关说明:本题为《算法竞赛入门经典(第2版)》习题 4-8
解法一:模拟
解决这题的核心是:判断下一个时间点的状态变化,以及判断状态是否发生了循环(说明不可能有全部学生醒来的情况)。做法就是按照时间每分钟进行模拟,更新每个学生的状态(需要根据上一分钟睡着人数比例判断能否入睡)。另外注意,这里的描述状态指的不是 “醒来” 和 “睡着”,而是在整个 醒来-睡着 周期中的状态序列,初始状态用 init_status 维护,此后只要发现下一状态 next_status 和初始状态一致,就说明开始了无限循环。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <bits/stdc++.h> using namespace std; struct Student { int awaken; int sleeping; int status; // [1, awaken] and [awaken+1, awaken+sleeping] }; int main() { int num_case = 0, num_student, a, b, c; while (cin >> num_student && num_student) { cout << "Case " << ++num_case << ": "; vector<Student> student; vector<int> init_status, next_status; int num_sleeping = 0; for (int i = 0; i < num_student; ++i) { cin >> a >> b >> c; student.push_back(Student{a, b, c}); init_status.push_back(c); if (c > a) num_sleeping++; } for (int time = 1;; ++time) { if (!num_sleeping) { cout << time << endl; break; } bool more_sleeping = (num_sleeping > num_student - num_sleeping); next_status.clear(); for (auto &s : student) { if (s.status == s.awaken + s.sleeping) // Will be Awaken s.status = 1, num_sleeping--; else if (s.status == s.awaken) // Wants to sleep again if (more_sleeping) s.status++, num_sleeping++; // Sleep else s.status = 1; // Struggle else s.status++; next_status.push_back(s.status); } if (next_status == init_status) { cout << "-1" << endl; break; } } // for time } // while case return 0; } |
1 |
#TODO |