森林的最大美麗值(二分+差分數組)

題目分析

求最小值的最大值，聯想到二分。

第一階段二段性分析

對于所有樹的高度都可以大于等于mid，那么我們可以確定高度小于mid的值一定也可以，但是此時我需要找的是最大的高度，那么mid一定比小于mid的值更大，所以小于mid的值我就不用管了，也就是我可以確定我能夠舍棄掉mid左邊的值。我還想要確定比mid更大的邊長是否也滿足條件，所以我要在mid的右邊繼續二分。

if (check(mid)) {l = mid;} //因為mid是符合條件的，所以我要留著它，而不是l=mid+1

對于所有樹的高度不能滿足都大于等于mid，那么我們可以確定高度大于mid的值一定也不滿足，所以大于等于mid的值我就不用管了，也就是我可以確定我能夠舍棄掉mid右邊的值。我還想要尋找比mid更小的高度是否能滿足條件，所以我要在mid的左邊繼續二分。

else { r = mid - 1; }//因為mid是不符合條件的，所以我不要留著它，而不是r=mid
//主要這里出現了減法，那么求mid那么應該是（l+r+1）/2

綜上該題滿足二段性，可以用二分，二分的板子就不說了，接下來說一下check函數如何寫。

第二階段寫check函數

check(u)要實現的作用是檢查能否在m天內讓所有樹的高度都大于等于u。

依次遍歷每一棵樹，如果當前樹的高度a[i]小于mid，那么需要給他增高，增高耗費的天數是(mid-a[i])。但是我們要注意一旦選擇增高不是只給一顆樹增高，而是給一個區間里的樹進行增高，那么這就涉及到區間修改，我們可以使用差分數組。現在重新考慮遍歷每一棵樹，當前樹的實際高度是a[i]+sum[i]，這里的sum[i]是差分數組的前綴和，如果a[i]+sum[i]<x，那么我們要給這棵樹增高，耗費的天數和增加的高度是x-a[i]-sum[i]，對于差分數組的變化是d[i]+=x-a[i]-sum[i]，d[i+k]-=x-a[i]-sum[i]，注意這里的i+k可能會有下標越界問題，所以要改成d[min(i+k,n+1)]-=x-a[i]-sum[i]，如果耗費的總天數超過了m，即cnt<0，就返回false，否則返回true。注意這里更改了d[i]后，對應的sum[i]也要隨之更新，否則這里d[i]的改變沒有傳遞下去。

public static boolean check(int x) {int d[] = new int[100010];int sum[] = new int[100010];int cnt = m;for(int i=1;i<=n;i++) {sum[i] =sum[i-1]+d[i];if(a[i]+sum[i]<x) {cnt-=x-a[i]-sum[i];d[i]+=x-a[i]-sum[i];d[Math.min(i+k,n+1)]+=sum[i]+a[i]-x;sum[i]+=x-a[i]-sum[i];if(cnt<0) return false;}}return true;
}

第三步二分范圍確定

那么這里的高度的最小值是1，最大值就是樹的最大高度，也就是1e9+1。

題目代碼

import java.util.Scanner;
public class Main {static int n,m,k;static int a[] = new int[100010];public static boolean check(int x) {int d[] = new int[100010];int sum[] = new int[100010];int cnt = m;for(int i=1;i<=n;i++) {sum[i] =sum[i-1]+d[i];if(a[i]+sum[i]<x) {cnt-=x-a[i]-sum[i];d[i]+=x-a[i]-sum[i];d[Math.min(i+k,n+1)]-=x-a[i]-sum[i];sum[i]+=x-a[i]-sum[i];if(cnt<0) return false;}}return true;}public static void main(String[] args) {Scanner scan = new Scanner(System.in);n=scan.nextInt();m=scan.nextInt();k=scan.nextInt();for(int i=1;i<=n;i++) a[i]=scan.nextInt();int l=1,r=1000000001;while(l<r) {int mid=(l+r+1)/2;if(check(mid)) l=mid;else r=mid-1;}System.out.print(l);}
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m, k;
int a[N];
int d[N], sum[N];bool check(int x) {for (int i = 1; i <= n; ++i) d[i]=0,sum[i]=0;int cnt = m;for (int i = 1; i <= n; ++i) {sum[i] = sum[i - 1] + d[i];if (a[i] + sum[i] < x) {cnt -= x - a[i] - sum[i];d[i] += x - a[i] - sum[i];if (i + k <= n) d[i + k] -= x - a[i] - sum[i];sum[i] += x - a[i] - sum[i];if (cnt < 0) return false;}}return true;
}int main() {cin >> n >> m >> k;for (int i = 1; i <= n; ++i) cin >> a[i];int l = 1, r = 1000000001;while (l < r) {int mid = (l + r + 1) / 2;if (check(mid)) l = mid;else r = mid - 1;}cout << l << endl;return 0;
}

def check(x):d = [0] * (n + 1)sum = [0] * (n + 1)cnt = mfor i in range(1, n + 1):sum[i] = sum[i - 1] + d[i]if a[i] + sum[i] < x:cnt -= x - a[i] - sum[i]d[i] += x - a[i] - sum[i]if i + k <= n:d[i + k] -= x - a[i] - sum[i]sum[i] += x - a[i] - sum[i]if cnt < 0:return Falsereturn Truen, m, k = map(int, input().split())
a = [0] + list(map(int, input().split()))  # Using 1-based indexingl, r = 1, 1000000001#+1e5
while l < r:mid = (l + r + 1) // 2if check(mid):l = midelse:r = mid - 1print(l)