POJ - 1006. Biorhythms 枚举技巧

Question

题目大意

人有三个生理高峰期，即体力、感情和智力，它们的周期长度分别为23 天、28 天和 33 天。每一个周期有一天是高峰，这一天很特别。由于这三个生理周期时间长短不同，所以通常三个周期的高峰不会落在同一天。现在想知道何时三个高峰落在同一天。

对于每个周期，给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）到下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为 10，下次出现三个高峰同天的时间是 12，则输出 2（注意这里不是 3）。

Sample Input

0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1

Sample Output

Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.

解析

简单枚举

• 这个思路很简单，从 d+1 天开始枚举每一个日期，看这个日期减去给定的初始日期能不能被对应的生理周期整除即可；
• 这个数据范围不是很大，所以也不会 TLE ；

代码:

#include <stdio.h>
 
// method one 
int main(int argc, char const **argv)
{     
    //freopen("in.txt","r",stdin);
    int kase = 0, p, e, i, d;
    while(~scanf("%d %d %d %d", &p, &e, &i, &d) && p != -1){ 
        for(int day = d+1; ; day++){     // notice begin from d + 1 
            if( (day-p)%23 == 0 && (day-e)%28 == 0 && (day-i)%33 == 0){
                printf("Case %d: the next triple peak occurs in %d days.\n", ++kase, day-d);
                break;
            }
        }
    }
    return 0;
}

---

优化枚举

优化的地方在:

• 我们可以先找到第一个体力高峰，然后找感情高峰的时候，日期 day 每次可以 +=23 ，因为以后的体力高峰一定是找到的那个日期加上 23 的倍数；
• 同理，我们找到了第一个既是体力高峰，又是情感高峰的日子之后，日期 day 每次可以 +=23*28 ，原因是一样的；
• 所以这就大大减少了枚举的天数 day ，时间得到加快；

代码:

#include <stdio.h>

//optimize method
int main(int argc, char const **argv)
{ 
    //freopen("in.txt", "r", stdin);
    int kase = 0, p, e, i, d, day;
    while(~scanf("%d %d %d %d", &p, &e, &i, &d) && p != -1){
        for(day = d+1; (day-p)%23; day++);
        for(; (day-e)%28; day += 23);
        for(; (day-i)%33; day += 23*28);
        printf("Case %d: the next triple peak occurs in %d days.\n", ++kase, day-d);
    }
    return 0;
}