Day3-Q-修补木桶 HihoCoder1362

本文主要是介绍Day3-Q-修补木桶 HihoCoder1362，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一只木桶能盛多少水，并不取决于桶壁上最高的那块木板，而恰恰取决于桶壁上最短的那块。

已知一个木桶的桶壁由N块木板组成，第i块木板的长度为Ai。

现在小Hi有一个快捷修补工具，每次可以使用修补工具将连续的不超过L块木板提高至任意高度。

已知修补工具一共可以使用M次(M*L<N)，如何修补才能使最短的那块木板最高呢？

注意: 木板是环形排列的，第N-1块、第N块和第1块也被视为连续的。

Input

第1行：3个正整数，N, M, L。分别表示木板数量，修补工具使用次数，修补工具每次可以同时修补的木板数。 1≤N≤1,000，1≤L≤20，M*L<N

第2行：N个正整数，依次表示每一块木板的高度Ai，1≤Ai≤100,000,000

Output

第1行：1个整数。表示使用修补工具后，最短木块的所能达到的最高高度

Sample Input

8 2 3
8 1 9 2 3 4 7 5

Sample Output

Hint

第一个修补工具覆盖[2 3 4]

第二个修补工具覆盖[5 8 1]

思路：可贪心验证+答案单调性，二分答案，验证时枚举起点即可，代码如下：

const int maxm = 100010;
const int INF = 0x7fffffff;int buf[maxm], N, M, L;bool check(int d) {int start = 0, sum;while(start < N) {sum = 0;for(int i = start; i < start + N;) {if(buf[i % N] < d) {i += L;sum++;} elsei++;}if(sum <= M)return true;start++;}return false;
}int main() {scanf("%d%d%d", &N, &M, &L);int l = INF, r = -INF, mid;for(int i = 0; i < N; ++i) {scanf("%d",&buf[i]);l = min(l, buf[i]), r = max(r, buf[i]);}while(l <= r) {mid = (l + r) >> 1;if(check(mid))l = mid + 1;elser = mid - 1;}printf("%d\n", r);return 0;
}