XieNaoban's Blog
0%

算法竞赛入门经典(第2版) 4-8UVa12108 - Extraordinarily Tired Students

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

书上具体所有题目：http://pan.baidu.com/s/1hssH0KO 代码：（Accepted，0 ms）

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
//UVa12108 - Extraordinarily Tired Students
#include<iostream>
struct how_cute_my_sleepy_boys_are {
	int a,//awaken period :		a>=1;
		b,//sleeping period :	b<=5;
		s,//state :				0醒着,1睡觉;
		t;//time :				睡/醒到什么时候;
}g[12];
int n, c, mi, cnt, T = 0;//cnt:统计睡着的人;mi:minute

int main()
{
	//freopen("in.txt", "r", stdin);
	while (scanf("%d", &n) && n != 0) {
		for (int I = 0;I < n;++I) {//读入数据
			scanf("%d%d%d", &g[I].a, &g[I].b, &c);
			g[I].s = (c > g[I].a ? 1 : 0);
			g[I].t = (g[I].s ? g[I].a + g[I].b - c + 1 : g[I].a - c + 1);
		}
		for (mi = 1;mi < 400;++mi) {//直接循环400分钟，不高兴做-1这一情况的循环检查了
			cnt = 0;
			for (int I = 0;I < n;++I)//计算本分钟的睡觉人数
				if (g[I].s == 1) ++cnt;
			if (!cnt) break;
			for (int I = 0;I < n;++I) {//睡或醒状态转换
				if (g[I].t != mi) continue;
				if (g[I].s == 1) g[I].s = 0, g[I].t += g[I].a;
				else if (cnt > n / 2) g[I].s = 1, g[I].t += g[I].b;
				else g[I].t += g[I].a;
			}
		}
		printf("Case %d: %d\n", ++T, !cnt ? mi : -1);
	}
	return 0;
}

题意：一个班级所有学生个个是特“困”生。每个人睡着和醒着有一定规律，那就是：醒着a分钟，然后想睡觉了，环顾四周，如果睡着的人比醒着的多，那我也睡，睡b分钟后再坚挺a分钟，否则直接再坚挺a分钟。简言之，也就是每醒a分钟就检查接下来是继续醒a分钟还是睡b分钟后再醒a分钟。（这“醒a分钟-睡b分钟”的a+b分钟被题目称为一个周期。）然后每个学生一上课就有个初始状态，是在各自醒-睡周期的第几分钟。求何时第一次全班醒着，还是说全班永远有人在睡觉。

分析：直接模拟每一分钟即可。struct一个结构体储存每个学生的状态，存放内容代码注释里已经很详细。本来t想存放的是还有几分钟到达目前状态的最后一分钟，但转念一想这样的话每分钟都要自减一次，直接存到哪一分钟更为便捷。具体模拟没用问题，很简单。 最大的问题是，就是老师上课永无天日的情况，永远没人醒着。本来我想做个数组存放每分钟的状态检查其是否构成循环，想想略麻烦，但是我看网上大家好多人都没检查，直接从一分钟检测到1000分钟（或其他很大的数字），1000分钟后还是没有全醒的情况就直接判定为“it'll never happen”。的确不够严谨但是很方便。最后昨晚睡觉前想了下，决定使用这个不严谨的方案。理由如下：

  1. 本来这每一分钟的模拟运算量就很小，还要每一分钟都去循环判断，有循环且循环很短的情况下不错，但是如果循环有几百分钟或很久后找到全醒的情况，综合这些情况下好像并不很合算。
  2. 题目的状态转换并不复杂，1000分钟甚至更短（我用的400分钟就AC了）该循环的绝对能循环了，当然数学上肯定能求出个这个分钟的最小值，也没必要去搞吧。
  3. 谁上个课上1000分钟啊！！！我一开始循环的150分钟，也已经2.5个小时了，结果WA，改成400分钟，AC了。400分钟已经6.666小时了。嗯，可以，老师学生们都很666。。。
  4. 听谁说过：竞赛题没人看你的代码是否优美，它也不关心你的算法，只要通过就行。→.→适当投机有益身心健康哈（大雾）。
  5. 懒得写循环检查了哈哈>_<。