京东烽火台试题及个人给出Java解题程序

声明：水货一枚，程序可能有不少bug，仅供参考！

试题：

保卫方案
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
战争游戏的至关重要环节就要到来了，这次的结果将决定王国的生死存亡，小B负责首都的防卫工作。首都处于一个四面环山的盆地中，周围的n个小山构成一个环，作为预警措施，小B计划在每个小山上设置一个观察哨，日夜不停的瞭望周围发生的情况。
一旦发生外敌入侵事件，山顶上的岗哨将点燃烽烟。若两个岗哨所在的山峰之间没有更高的山峰遮挡且两者之间有相连通路，则岗哨可以观察到另一个山峰上的烽烟是否点燃。由于小山处于环上，任意两个小山之间存在两个不同的连接通路。满足上述不遮挡的条件下，一座山峰上岗哨点燃的烽烟至少可以通过一条通路被另一端观察到。对于任意相邻的岗哨，一端的岗哨一定可以发现一端点燃的烽烟。
小B设计的这种保卫方案的一个重要特性是能够观测到对方烽烟的岗哨对的数量，她希望你能够帮她解决这个问题。
输入
输入中有多组测试数据。每组测试数据的第一行为一个整数n（3<=n <=10^6），为首都周围的小山数量，第二行为n个整数，依次表示小山的高度h，（1<=h<=10^9）。
输出
对每组测试数据，在单独的一行中输出能相互观察到的岗哨的对数。

样例输入
5
1 2 4 5 3
样例输出
7

Java程序：

import java.util.Scanner;

/**
 * 思路说明 1.将数组分为5部分，x1,m,x2,n,x3；
 * 2.m为第一个想要判断的项，n为第二个判断项，x1为m前所有项的集合,x2为m和n之间所有项的集合,x3为n后*所有项的集合，其中x1,x2和x3均有可能是空集，后面有处理；
 * 3.要想能看到对方，情况分为两种，m>=max(x2)&&n>=max(x2)||m>max(x1,x3)&&n>max(x1,x3); 其他情况是这两种情况的子集，不必考虑；
 * 
 * @author Levi_Lin
 * 
 */
public class SeeHill {
  public static void main(String[] args) {
    Scanner read = new Scanner(System.in);
    while (read.hasNext()) {
      int result = 0;// 建立变量，准备存入结果；
      int num = read.nextInt();
      int[] hill = new int[num];
      for (int i = 0; i < num; i++)
        hill[i] = read.nextInt();
      for (int i = 0; i < num; i++) {
        for (int j = i + 1; j < num; j++) {
          int x1 = getMax(hill, 0, i);
          int x2 = getMax(hill, i + 1, j);
          int x3 = getMax(hill, j + 1, num);
          if ((hill[i] >= x2 && hill[j] >= x2)
              || (hill[i] > getMax(x1, x3) && hill[j] >= getMax(x1, x3)))
            result++;
        }
      }
      System.out.println(result);
    }
    read.close();
  }

  /**
   * 求两数最大值，和下面的函数重载：
   * 
   * @return 两者最大的值
   */
  public static int getMax(int a, int b) {
    return a >= b ? a : b;
  }

  /**
   * 说明：left>=right时说明该集合为空集，返回-1，说明之间没有屏障，可以任意穿越该集合观看
   * 
   * @param arr 需要找出较大值的数组
   * @param left数组角标左边界（包含）
   * @param right数组角标右边界（不包含）
   * @return返回较大值；
   */
  public static int getMax(int[] arr, int left, int right) {
    if (left >= right)
      return -1;
    int max = arr[left];
    for (int i = left + 1; i < right; i++)
      if (arr[i] > max)
        max = arr[i];
    return max;
  }
}

#Java工程师#