UVa 12108 Extraordinarily Tired Students(特别困的学生)

时间:2021-09-12 21:57:56

UVa 12108 Extraordinarily Tired Students(特别困的学生)UVa 12108 Extraordinarily Tired Students(特别困的学生)UVa 12108 Extraordinarily Tired Students(特别困的学生)


题意:

每个学生(1<=n<=10)存在一个awake-sleep周期,当这个学生到awake的最后一刻时,他要判断当前睡觉和醒的学生的人数,如果睡觉的人数绝对大于醒着的人数,那么他要继续保持清醒a分钟,否则就进入睡觉状态。

给出n个学生的清醒周期和睡觉周期以及初始时刻处于周期的时刻,判断什么时刻全班同学都清醒着,如果不存在这样的时刻,那么就输出-1.


分析:

只需要计算每个时刻全班的清醒人数和睡觉人数:更新每位同学的状态。然后判断是否awake人数==n即可。

完全模拟!


难点:

①对每个学生每个时刻参量的描述,可用结构体!

②每个时刻的状态判断

③大的循环时间的选择


参考链接

#include <stdio.h>
#include <string.h>
#define maxn 15
struct STUDENT {
	int A;//清醒A分钟
	int B;//睡B分钟
	int C;//当前处于的周期时间C分钟
	int D;//周期总时间
	int is_sleep;//当前时间是不是睡着
}st[maxn];
int cases = 0, n;
int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	while (~scanf("%d", &n) && n)
	{
		int ALL = 1;//所有学生的醒睡总周期
		int awake = 0, sleep = 0;//全班清醒人数和睡觉人数
		for (int i = 0;i < n;i++)
		{
			scanf("%d%d%d", &st[i].A, &st[i].B, &st[i].C);
			st[i].D = st[i].A + st[i].B;
			if (st[i].C <= st[i].A)
			{
				st[i].is_sleep = 0;
				awake++;
			}
			else
			{
				st[i].is_sleep = 1;
				sleep++;
			}
			ALL *= st[i].D;
		}
		int time;//当前时间
		int flag=0;//标记是否存在全班都清醒的时刻
		for (time = 1;time <= ALL;time++)//只需要判断从初始回到初始这个时间段的情况
		{
			if (awake == n)
			{
				flag = 1;
				break;
			}
			int pre_sleep = sleep;//pre_sleep是上一时刻睡觉人数
			int pre_awake = awake;//pre_awake是上一时刻清醒人数
			for (int i = 0;i < n;i++)
			{
				st[i].C++;//下面就在i位学生周期的C时刻该学生的状态进行讨论
				//只有两种变化(醒->睡和睡->醒)时才需更新状态,其余情况只需C叠加
				if (st[i].C == (st[i].D + 1))//睡->醒
				{
					st[i].C = 1;
					st[i].is_sleep = 0;
					sleep--;
					awake++;
				}
				else if (st[i].C == (st[i].A + 1))//醒->睡
				{
					if (pre_sleep > pre_awake)
					{ //这点很重要!sleep和awake是变化当前状态,而需要判断的实际上是上一时刻
						st[i].is_sleep = 1;
						sleep++;
						awake--;
					}
					else st[i].C = 1;
				}
			}
		}
		if (flag) printf("Case %d: %d\n", ++cases, time);
		else printf("Case %d: %d\n", ++cases, -1);
	}
	return 0;
}