102 可见的山峰对数量
Table of Contents

ac

链接：https://www.nowcoder.com/questionTerminal/80d076bcea594b86ba55b913de4c069d?f=discussion
来源：牛客网

一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如，{3,1,2,4,5}，{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。3->1->2->4->5->3 方向叫作 next 方向(逆时针)，3->5->4->2->1->3 方向叫作 last 方向(顺时针)。
山峰 A 和 山峰 B 能够相互看见的条件为:
1. 如果 A 和 B 是同一座山，认为不能相互看见。
2. 如果 A 和 B 是不同的山，并且在环中相邻，认为可以相互看见。
3. 如果 A 和 B 是不同的山，并且在环中不相邻，假设两座山高度的最小值为 min。如果 A 通过 next 方向到 B 的途中没有高度比 min 大的山峰，或者 A 通过 last 方向到 B 的途中没有高度比 min 大的山峰，认为 A 和 B 可以相互看见。

问题如下：
给定一个不含有负数且没有重复值的数组 arr，请问有多少对山峰能够相互看见？

last方向（顺时针）

          ---
       --       --
  最大值           次大值
      --        --
        y      z
          -  -
           x

next 方向 （逆时针）

存在一个最大，次大

假设x既不是最大，也不是最小
x的last方向上第一个大于x假设为y,y可能就是最大的
 x的next方向上第一个大x假设为z，z可能是此大的

x 在last 方向上没到达y 之前遇到的所有山峰高度都小于x
x 在next 方向上没到达z 之前遇到的所有山峰高度都小于x

(i-2) * 2 + 次大值到最大值这一对 （i-2即除了最大，此大外）

结论：

环形结构中有i 座山峰时（i>2），可见山峰对的数量为2×i-3

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt(); // n 表示 山峰的数量
            // 山峰的高度数组等于 1 - p 的 p! 个全排列按字典序排序后的第 m 个全排列的前 n 项
            int p = sc.nextInt();
            int m = sc.nextInt();
            if(n > 1) {
                System.out.println(2 * n - 3);
            }else {
                System.out.println(0);
            }
        }
    }

}