蹄球

题目

链接：1738. 蹄球 - AcWing题库

为了准备即将到来的蹄球锦标赛，Farmer John 正在训练他的 N 头奶牛（方便起见，编号为 1…N）进行传球。

这些奶牛在牛棚一侧沿直线排列，第 i 号奶牛位于距离牛棚 xi 的地方。

每头奶牛都在不同的位置上。

在训练开始的时候，Farmer John 会将若干个球传给不同的奶牛。

当第 i 号奶牛接到球时，无论是从 Farmer John 或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会将球传给这些奶牛中最左边的那头奶牛。）。

为了使所有奶牛都有机会练习到传球，Farmer John 想要确保每头奶牛都持球至少一次。

帮助他求出为了达到这一目的他开始时至少要传出的球的数量。

假设他在开始的时候能将球传给最适当的一组奶牛。

代码

import java.util.*;


public class Main {
    static int N = 100010;
    static int n, ans = 0;
    static int[] a = new int[110];
    static int[] b = new int[110];
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        for(int i = 1; i <= n; i ++)
            a[i] = inScanner.nextInt();
        Arrays.sort(a, 1, n + 1);
        for(int i = 1; i < n; i ++)
            a[i] = a[i + 1] - a[i];
        for(int i = 2; i < n; i ++)
            b[i] = a[i] >= a[i - 1] ? 1 : -1;
        b[1] = -1;
        b[n] = 1;
        for(int i = 1; i < n; i ++)
            if(b[i] < 0 && b[i + 1] > 0)
            {
                ans ++;
                if(b[i - 1] < 0 && b [i + 2] > 0)
                    ans ++;
            }
        System.out.println(ans);
        inScanner.close();
    }
}