題目地址：?https://vjudge.net/problem/OpenJ_Bailian-4148

人生來就有三個(gè)生理周期，分別為體力周期、感情周期和智力周期，它們的周期長度分別為23天、28天和33天。每一個(gè)周期中有一天是高峰。在高峰這天，人會(huì)在相應(yīng)的方面表現(xiàn)出色。例如，在智力周期的高峰，人會(huì)思維敏捷，注意力容易高度集中。因?yàn)槿齻€(gè)周期的長度不同，所以通常三個(gè)周期的高峰不會(huì)落在同一天。對(duì)于每個(gè)人，想知道何時(shí)三個(gè)高峰落在同一天。對(duì)于每個(gè)周期，會(huì)給出從當(dāng)前年份的第一天開始，到出現(xiàn)高峰的天數(shù)（不一定是第一次高峰出現(xiàn)的時(shí)間）。給定一個(gè)從當(dāng)年第一天開始的天數(shù)，你的任務(wù)是輸出從給定時(shí)間開始（不包括給定時(shí)間），下一次三個(gè)高峰落在同一天的時(shí)間（距給定時(shí)間的天數(shù)）。例如：給定時(shí)間為10，下次出現(xiàn)三個(gè)高峰同一天的時(shí)間是12，則輸出2（注意這里不是3）。

輸入輸入包含多組數(shù)據(jù)，每一組數(shù)據(jù)由四個(gè)整數(shù)組成，數(shù)據(jù)以-1 -1 -1 -1 結(jié)束。
對(duì)于四個(gè)整數(shù)p, e, i和d，p, e, i分別表示體力、情感和智力高峰出現(xiàn)的時(shí)間（時(shí)間從當(dāng)年的第一天開始計(jì)算）。d是給定的時(shí)間，可能小于p, e或i。所有給定時(shí)間是非負(fù)的并且小于或等于365，所求的時(shí)間小于或等于21252。輸出從給定時(shí)間起，下一次三個(gè)高峰同一天的時(shí)間（距離給定時(shí)間的天數(shù)）。

樣例輸入

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

樣例輸出

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.


1、未經(jīng)優(yōu)化的暴力枚舉
有2個(gè)需要注意的地方： (1)j要從d+1開始枚舉，不能從1開始枚舉。因?yàn)閐有可能比下一次出現(xiàn)的時(shí)間大。例如輸入為 1 19 14 48時(shí)，如果只是從1開始枚舉，結(jié)果將會(huì)為-1
　　　　　　　　　　　(2)是結(jié)果j-d <= 21252，而不是j <= 21252 1 #include <iostream> 2 #include <queue> 3 using namespace std; 4 5 6 int main() 7 { 8 int p, e, i, d; 9 int num = 0; 10 while (1) 11 { 12 ++num; 13 cin >> p >> e >> i >> d; 14 if (p == -1 && e == -1 && i == -1 && d == -1) 15 break; 16 17 int j; 18 for (j = d+1; j-d <= 21252; ++j) //注意j要從d+1開始枚舉，且是j-d <= 21252 ！！ 19 { 20 if ((j - p) % 23 == 0 && (j - e) % 28 == 0 && (j - i) % 33 == 0) 21 { 22 printf("Case %d: the next triple peak occurs in %d days.\n", num, j-d); 23 break; 24 } 25 } 26 } 27 28 29 30 31 return 0; 32 }

?

2、優(yōu)化后的枚舉算法：

　　檢索時(shí)可以利用已經(jīng)發(fā)現(xiàn)的高峰值來加速搜索的過程。例如，若發(fā)現(xiàn)第102天是體力的高峰值，那么第103,104,105，...，124天都不可能是體力、情感和智力高峰均出現(xiàn)的時(shí)間，因此可以直接跳到第102+23=125天。這個(gè)優(yōu)化策略可以概括為：若某項(xiàng)高峰值的時(shí)間已經(jīng)出現(xiàn)，則該高峰值的出現(xiàn)周期可以作為搜索步長。

1 #include <iostream> 2 3 using namespace std; 4 5 int main() 6 { 7 int p, e, i, d; 8 int num = 0; 9 while (1) 10 { 11 ++num; 12 cin >> p >> e >> i >> d; 13 if (p == -1 && e == -1 && i == -1 && d == -1) 14 break; 15 16 int j; 17 for (j = d + 1; (j - p) % 23; ++j); 18 for (; (j - e) % 28; j = j + 23); 19 for (; (j - i) % 33; j = j + 23 * 28); 20 printf("Case %d: the next triple peak occurs in %d days.\n", num, j-d); 21 22 } 23 24 25 return 0; 26 }

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/FengZeng666/p/10413614.html

總結(jié)

以上是生活随笔為你收集整理的OpenJ_Bailian 4148 生理周期的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。