打井
时间限制:2000ms 内存限制:512MiB
题目描述
直线上有 n 处位置，第 i 处位置的高度为正整数 x_i 。 你可以进行不超过 m 次挖掘，每次挖掘可以选择一个 i ，讲它的的海拔 x_i 减去 1 。
你需要挖一口井，任何一处位置 x_i 如果变成 0 ，则打井成功。此时不能继续向下挖 x_i ，即所有的 x_i 最多减到 0 ，必须保持他是正整数。
为了让人们到井口打水更加安全，还需要任意相邻两个位置的落差的最大值尽量小，即最小化 z ，其中
现在需要输出最小的 z ，和达到这个条件前提下的打井位置。
输入格式
第一行两个正整数 n, m 。保证 1 \le n\le 10^6 ， 1\le m\le 10^{18} 。
第二行 n 个正整数 x_1,x_2,\dots,x_n 。保证 x_i\le 10^9 。
输出格式
输出 k 和 z 。数据保证方案一定存在。
如果有多个打井选择 k ，可以输出任何一个。
题解
思路：
最大值最小，一眼二分答案
因为 z = \max_{i=1}^{n-1}|x_i-x_{i+1}| 是求一个最大值
我们要最小化这个最大值，所以使用二分答案，使用 check 验证
check:
直接枚举打井位置肯定是不行的，因为时间复杂度 \Theta(n^2)
考虑从在 i 打井递推到在 i+1 打井
我们发现，在 i 打井的高度数组是这样的
a_1,a_2,...,xz,(x-1)z,(x-2)z,...2z,z,0,z,2z,...,(y-2)z,(y-1)z,yz,...,a_{n-1},a_n
不难发现， xz 和 yz 的位置是在一直变大的，所以可以走指针
现在考虑花费次数的问题
设 xz 和 yz 的位置在 l 和 r 上
从 l 开始枚举，设这一位是 j ，则如果 a_j≥(x+j-l+1)z ，将 l=j 停止枚举
从 r 开始枚举，设这一位是 c ，则需要找到最后一个使得 a_c≥(y+c-r-1)z ，将其赋值给 r
至于 l 到 r 的花费次数，拿前缀和再瞎搞一下就算出来了
时间复杂度：(优秀的) \Theta(n)
总时间复杂度： \Theta(n \log w) ， w 表示 x_i 的值域
(注：需要注意原数组对于最大差值 z 的次数花费)
