MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 12108 - Extraordinarily Tired Students
AOAPC II

UVaOJ 12108 - Extraordinarily Tired Students

Chai
2021-11-24 0:00:00在线评测阅读 368

问题描述

p12108

原题链接:UVaOJ 12108 - Extraordinarily Tired Students

相关说明:本题为《算法竞赛入门经典(第2版)》习题 4-8

解法一:模拟

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

C++
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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz