算法：POJ1006 三重峰值问题

浏览数：26 / 时间：2015年06月08日

这题有直接套公式的解法

这里提供一个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.");
        }

    }
}