UVA

** 题目链接 ** UVA - 12108

** _ 题目思路: _ **

用f[i]来纪录每个学生当前的状态(是否睡觉)
用now[i]来纪录每个学生处于当前状态的总时间
用first[i]来纪录所有学生最初时处于第几分钟,用于循环中判断是否无解(若后面重复到此状态即为无解)
特殊点:
学生a在第i分钟准备睡觉,对于是否进行睡觉的判断是由第 i - 1分钟得出的。

** _ 代码: _ **

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <set>
#include <stack>
#include <stdlib.h>
#include <time.h>

using namespace std;

int va[11];//清醒周期长度
int vb[11];//睡觉周期长度
int now[11];//处于当前状态第几分钟
int first[11];//最初处于第几分钟
int f[11];//是否睡觉

bool isall(int n)//判断是否与最初状态重合,即判断是否无解
{
    for(int i=0;i<n;i++)
    {
        int t = 0;
        if(f[i])
            t = va[i];//加上清醒周期的长度,与最初值保持一致
        if(now[i] + t != first[i])
            return false;
    }
    return true;
}

int main()
{
    int n, T=0;
    while(cin>>n && n)
    {
        ++T;
        int time = 1;//当前时间
        int num = 0;//睡觉总人数
        for(int i=0;i<n;i++)
        {
            cin>>va[i]>>vb[i]>>now[i];
            first[i] = now[i];
            if(now[i] > va[i])
            {
                f[i] = 1;
                ++num;
                now[i] -= va[i];
            }
            else
                f[i] = 0;
        }
        while(1)
        {
            if(num == 0)//全部清醒,退出循环
                break;
            int t = 0;//本分钟睡觉人数的增减量
            for(int i=0;i<n;i++)
            {
                ++now[i];
                if(f[i])//睡
                {
                    if(now[i] > vb[i])
                    {//开始清醒
                        now[i] = 1;
                        f[i] = 0;
                        --t;
                    }
                }
                else
                {
                    if(now[i] > va[i])
                    {
                        now[i] = 1;
                        if(num*2 > n)//上一分钟睡觉人数是否符合睡觉条件
                        {
                            f[i] = 1;
                            ++t;
                        }
                    }
                }

            }
            num += t;
            if(isall(n))
            {
                time = -1;
                break;
            }
            ++time;
        }
        printf("Case %d: %d\n", T, time);
    }
    return 0;
}