2977 : 生理周期

---

總時間限制: 1000ms 內存限制: 65536kB

---

描述
人生來就有三個生理周期，分別為體力、感情和智力周期，它們的周期長度為23天、28天和33天。每一個周期中有一天是高峰。在高峰這天，人會在相應的方面表現出色。例如，智力周期的高峰，人會思維敏捷，精力容易高度集中。因為三個周期的周長不同，所以通常三個周期的高峰不會落在同一天。對于每個人，我們想知道何時三個高峰落在同一天。對于每個周期，我們會給出從當前年份的第一天開始，到出現高峰的天數（不一定是第一次高峰出現的時間）。你的任務是給定一個從當年第一天開始數的天數，輸出從給定時間開始（不包括給定時間）下一次三個高峰落在同一天的時間（距給定時間的天數）。例如：給定時間為10，下次出現三個高峰同天的時間是12，則輸出2（注意這里不是3）。

輸入
一行，包含四個整數：p, e, i和d，相鄰兩個整數之間用單個空格隔開。 p, e, i分別表示體力、情感和智力高峰出現的時間（時間從當年的第一天開始計算）。d 是給定的時間，可能小于p, e, 或 i。 所有給定時間是非負的并且小于等于365, 所求的時間小于等于21252。
輸出
一個整數，即從給定時間起，下一次三個高峰同天的時間（距離給定時間的天數）。
樣例輸入
4 5 6 7
樣例輸出
16994
來源
East Central North America 1999, POJ 1006， 程序設計實習2007
解題思路： 枚舉
考察問題，得到如下的結論
1、解空間存在于2-21252，經計算，21252是23，28，33的一個公倍數。
2、描述里有“d 是給定的時間，可能小于p, e, 或 i”，然而目標解至少大于等于怕p,e,i的最大值，或許這里是個陷阱。用余數關系%可以避免。
3、最直接的思路是從Time = d+1開始，逐一嘗試Time是否為目標解。在可接受的的思路之內，顯然這個最直接的思路效率最低（進行了很多無謂的嘗試）。考察Time，（Time - p） % 23 == 0 && （Time - e） % 28 == 0 && （Time - i) % 33 == 0時，目標解成立。
1）在第一個條件（Time - p） % 23 == 0成立之前，應該逐一考察Time使得條件成立；
2）在條件1成立的基礎上，為滿足第一個條件（Time - p） % 23 == 0一直成立，Time的步長起碼最低可以從23起（見code中Time += time_1），并在此迭代的過程中考察條件2 （Time - e） % 28 == 0；
3）在得到同時滿足（Time - p） % 23 == 0和（Time - e） % 28 == 0的Time之后，類似的思路，Time的步長應取23 * 28（見code中Time += time_2），直至條件3成立，退出循環，得到結果。
彩蛋一坨：目標結果必然小于等于21252，ans = 21252 > Time - d ? Time - d : 21252;這里是純屬無聊。

#include <iostream> //#define LOCAL int p, e, i, d, Time, ans; int time_1 = 23, time_2 = 23 * 28; int main() { #ifdef LOCAL //不知道的讀者，這只是方便調試的小技巧freopen("in.txt", "r", stdin); #endifscanf("%d%d%d%d", &p,&e,&i,&d);Time = d + 1;while ((Time - p) % 23 != 0) ++Time;while ((Time - e) % 28 != 0) Time += time_1;while ((Time - i) % 33 != 0) Time += time_2;ans = 21252 > Time - d ? Time - d : 21252;printf("%d\n", ans);return 0; }

---

總結

以上是生活随笔為你收集整理的POJ 2977 生理周期 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。