2018 Bronze February p2

题目

有 n 头牛站在不同的位置，每头牛只能传球给离自己最近的牛（如果有多头牛距离相同传给左边的），求需要多少球能让所有奶牛都传一次球。

思路

假设让每头奶牛都传一次球，并记录每头奶牛收到球的数量；如果有奶牛收到球的数量为 0，或有两头奶牛相互传球且不会有新的球进来，则需要球的数量加一。

复杂度分析

排序数组的复杂度为n logn，过程中需要遍历两次数组，复杂度都为 O(n)，奶牛数量最大为 100，所以不会超时