首页 > 代码库 > 算法:POJ1006 三重峰值问题

算法:POJ1006 三重峰值问题

这题有直接套公式的解法

这里提供一个O(n)的解法。

package practice;import java.io.BufferedInputStream;import java.util.Scanner;/** *  *  * @author caiyu * @date 2014-11-4 */public class POJ1006 {    public static void main(String[] args) {        Scanner cin = new Scanner(new BufferedInputStream(System.in));        while (true) {            int p = cin.nextInt();            if (p < 0)                break;            int e = cin.nextInt();            if (e < 0)                break;            int i = cin.nextInt();            if (i < 0)                break;            int d = cin.nextInt();            if (d < 0)                break;            int x = 1, y = 1, z = 1;            int ty = 0, tx = 0, tz = 0;            boolean fx = true, fy = true, fz = true;            int temp = 0;            while (true) {                if (fy) {                    if (ty < 21252)                        ty = e + 28 * y++ - d;                    else                        break;                    if ((ty - p + d) % 23 == 0) {                        if (ty > temp) {                            temp = ty;                            fz = true;                            fx = true;                            fy = false;                        } else if (ty == temp) {                            fy = false;                        }                    }                }                if (fz) {                    if (tz < 21252)                        tz = i + 33 * z++ - d;                    else                        break;                    if ((tz - p + d) % 23 == 0) {                        if (tz > temp) {                            temp = tz;                            fx = true;                            fy = true;                            fz = false;                        } else if (tz == temp) {                            fz = false;                        }                    }                }                if (fx) {                    if (tx < 21252)                        tx = p + 23 * x++ - d;                    else                        break;                    if ((tx - e + d) % 28 == 0) {                        if (tx > temp) {                            temp = tx;                            fy = true;                            fz = true;                            fx = false;                        } else if (tx == temp) {                            fx = false;                        }                    }                }                if (!fx && !fy && !fz)                    break;            }            System.out.println("Case 1: the next triple peak occurs in " + temp                    + " days.");        }    }}

 

算法:POJ1006 三重峰值问题