首页 > 代码库 > UVA 12108 特别困的学生

UVA 12108 特别困的学生

题意:

每个学生有一个“睡眠-清醒” 周期, 第i个学生醒Ai分钟睡 Bi分钟, 初始处在他的周期的第Ci分钟, 临睡时会查看全班睡眠人数是否>清醒人数, 是则进入睡眠周期, 不然保持清醒Ai分钟, 问多久后全部学生都清醒

分析:

题目求的是清醒人数, 那么我们可以把清醒人数设为一个变量, 设一个足够长的时间轴作为循环, 当清醒人数为N时跳出循环, 否则到了时间轴尾就输出-1。 题目给定的Ci其实很好的帮我们处理了“当前时间的问题”, 可以这样想, 时间轴每一点都进行ci的判断, <ai 则清醒人数++(清醒人数每一点初始化为0), 然后如果ci == ai 就判断人数, 如果不符合将ci回归到1, 同时当ci = ai + bi时也要回归到1

代码:

#include <stdio.h>
using namespace std;
int n;
int A[13], B[13], C[13];
int awake;
int main()
{
    int kase = 1;
    while(scanf("%d", &n) != EOF && n){
        awake = 0;
        for(int i = 0; i < n; i++){
            scanf("%d %d %d", &A[i], &B[i], &C[i]);

        }
        int time = 1;
        for(time = 1; time < 10000; time ++)//time axis set large enough.
        {
            awake = 0;
            for(int i = 0; i < n; i++){
                if(C[i] <= A[i])
                    awake++;
            }
            if(awake == n) break;
            for(int i = 0; i < n; i++){
                if(C[i] == A[i] + B[i] || C[i] == A[i] && awake >= n - awake )// n-awake, student who have slept
                    C[i] = 0;
                C[i]++;
            }
        }
        if(time == 10000) printf("Case %d: -1\n",kase++);
        else printf("Case %d: %d\n",kase++, time);
    }
    return 0;
}

 

 

UVA 12108 特别困的学生