最佳牛围栏

acwing习题链接

思路

  • 主要使用前缀和+二分的思路
  • 使用二分找到平均值最大值。平均值显然在0到最大值之间。考虑将数组中的所有数都减去平均值，则当减去的数小于平均值时，能找到一个区间和大于0，当减去的数大于最大平均值时，没有区间和大于0。因此问题满足该二分的性质，可以使用二分。而问题的核心就转化了为求区间和。

  • 如何进行二分过程中的判断，可以使用前缀和的方式计算区间的和。其时间复杂度为O(N),而二分的时间复杂度为O(logN),因此原问题的时间复杂度为O(NlogN),。

    总结

  • 我们常见的二分，看上去是对数组进行二分查找或是该数组满足一个可以二分的性质，数组左侧满足，数组右侧不满足。

  • 本题，二分的性质不是数组左右侧满足的性质。而是对二分区间，我们想要得到的结果左右侧有可以二分的性质。而二分的过程就是找到这个结果的过程，判断是对整个数组进行一定的计算，验证该性质。