愤怒的FlappyBird

描述

FlappyBird是一款简单又困难的手机游戏，游戏中玩家必须控制一只胖乎乎的FlappyBird，跨越由各种不同长度水管所组成的障碍。如下图所示：

由于被大家称为胖乎乎的小鸟，所以这FlappyBird很愤怒，决定横冲直撞，撞掉一条直线上的所有柱子。

为了简化问题，增加问题的趣味性。把场景设定为长度为NN，高度为HH的一条通道。每一个单位长度有一个柱子，且奇数位置的柱子是从下往上长的，偶数位置的柱子是从上往下长的(如下图所示)。FlappyBird会撞坏一条直线上的所有柱子。作为一个游戏安全评估师，JM想知道FlappyBird有多少种飞行高度，会撞坏最少柱子数量。

**注意：**FlappyBird飞行时只会选择某一高度的中间飞行，如上图所示。不会飞行在相邻两个高度的交界处。即：如果通道高度为55，从上往下长度为22的柱子和从下往上长度为33的柱子是永远不可能同时被撞坏的。

输入

输入第一行包含两个整数N，HN，H，分别表示柱子的数量以及通道的高度。

接下来下来输入NN行，每行一个整数A_iA**i，表示柱子的长度。

奇数行根柱子表示柱子从下往上，长度为A_iA**i；偶数行表示柱子从上往下场地为A_iA**i.

输出

输出两个整数，分别表示最少撞坏柱子数以及可能的高度数量。

样例

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

输出复制

7 2

输入复制

6 7
1
5
3
3
5
1

输出复制

2 3

提示

样例1解释

在飞行高度位4的位置，撞坏的柱子数为8

如上图所示

在高度11处飞行，会撞坏77根柱子；

在高度22处飞行，会撞坏88根柱子；

在高度33处飞行，会撞坏1010根柱子；

在高度44处飞行，会撞坏88根柱子；

在高度55处飞行，会撞坏77根柱子；

所以最少会撞坏柱子数位77，共有22种飞行高度。

数据规模

对于30%30%的数据，2 \le N \cdot H \le 10^62≤N⋅H≤106。

对于100%100%的数据，2 \le N \le 2\cdot 10^{5, 2 \le H \le 5 \cdot 10}5,0 \le A_i \le H2≤N≤2⋅105,2≤H≤5⋅105,0≤A**i≤H.

**主要解决方法就是差分和前缀和，用差分标记出，每一层高度会撞断下面柱子的数量和上面柱子的数量 高度没有超过下面柱子的高度会被撞断 ,那么高度为i时撞断的柱子为down[i] **

标记上面柱子的时候需要转换一下 h-arr[i]+1 表示 高度超过这个值才会撞断柱子 那么第i层撞断的柱子就是up[1]-up[i]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class H愤怒的FlappyBird {

    static int max= (int) (1e6+10);
    static int[] down=new int[max];
    static int[] up=new int[max];
    //java快读输入
    static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int nexInt() throws IOException {in.nextToken(); return(int) in.nval;}
    static int n,h,min=Integer.MAX_VALUE,sum;
    public static void main(String[] args) throws IOException {

        n=nexInt();
        h=nexInt();
        int [] arr=new int[n+1];
        for (int i = 1; i <=n; i++) {
            arr[i]=nexInt();
               //差分 标记出下面柱子所在区间的值
               if(i%2==1){
                   down[1]++;
                   down[arr[i]+1]--;

                   //差分标记出上面柱子所在区间的值
               }else if(i%2==0){
                    up[1]++;
                    up[h-arr[i]+1]--;
               }
         }
        for (int i = 1; i <=h; i++) {
           //前缀和恢复差分标记的值
            down[i]=down[i]+down[i-1];
            //前缀和恢复差分标记的值
            up[i]=up[i]+up[i-1];
               //第i层装断的就等于下面第i层值，加上，上面(up[1]-up[i])的值
          int c= down[i]+up[1]-up[i];
             //最小撞断了多少
            if(c<min){
              min=c;
              sum=1;
          }else if(min==c)sum++;
            //最少有多少个
        }
        System.out.println(min+" "+sum);

    }
}