UVaOJ 12108 – Extraordinarily Tired Students

问题描述

原题链接：UVaOJ 12108 - Extraordinarily Tired Students

解法一：模拟

解决这题的核心是：判断下一个时间点的状态变化，以及判断状态是否发生了循环（说明不可能有全部学生醒来的情况）。做法就是按照时间每分钟进行模拟，更新每个学生的状态（需要根据上一分钟睡着人数比例判断能否入睡）。另外注意，这里的描述状态指的不是 “醒来” 和 “睡着”，而是在整个醒来-睡着周期中的状态序列，初始状态用 init_status 维护，此后只要发现下一状态 next_status 和初始状态一致，就说明开始了无限循环。

#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;
}

#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;

}

#TODO

#TODO

AOAPC II UVaOJ