移山

[题目链接](https://www.nowcoder.com/practice/d917144251c6433ca633112d83c4422a)

思路

给定 个山头的初始高度和 次施法操作，每次操作将区间 内的所有山头高度减少 。问最早在第几次操作后，存在某个山头高度 。

关键观察：答案具有单调性

如果前 次操作后已经有山头 ，那么前 次操作后也一定有（因为只减不加）。因此可以二分答案。

二分 + 差分数组

对于二分的 ，我们需要快速判断：执行前 次操作后，是否存在某个山头高度 。

每次操作是区间减法，可以用差分数组在 时间内记录每次操作，最后做一次前缀和即可得到每个位置的总减少量。遍历所有山头，检查 即可。

复杂度

• 二分 次
• 每次检查需要 （构建差分数组 + 前缀和扫描）
• 总复杂度

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<long long> a(n+1);
    for(int i = 1; i <= n; i++) cin >> a[i];

    vector<int> L(m+1), R(m+1);
    vector<long long> H(m+1);
    for(int i = 1; i <= m; i++) cin >> L[i] >> R[i] >> H[i];

    int lo = 1, hi = m, ans = m;
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        vector<long long> diff(n+2, 0);
        for(int i = 1; i <= mid; i++){
            diff[L[i]] += H[i];
            diff[R[i]+1] -= H[i];
        }
        long long sum = 0;
        bool found = false;
        for(int i = 1; i <= n; i++){
            sum += diff[i];
            if(a[i] - sum <= 0){
                found = true;
                break;
            }
        }
        if(found){
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }

    cout << ans << endl;
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        long[] a = new long[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }

        int[] L = new int[m + 1], R = new int[m + 1];
        long[] H = new long[m + 1];
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            L[i] = Integer.parseInt(st.nextToken());
            R[i] = Integer.parseInt(st.nextToken());
            H[i] = Long.parseLong(st.nextToken());
        }

        int lo = 1, hi = m, ans = m;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            long[] diff = new long[n + 2];
            for (int i = 1; i <= mid; i++) {
                diff[L[i]] += H[i];
                diff[R[i] + 1] -= H[i];
            }
            long sum = 0;
            boolean found = false;
            for (int i = 1; i <= n; i++) {
                sum += diff[i];
                if (a[i] - sum <= 0) {
                    found = true;
                    break;
                }
            }
            if (found) {
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }

        System.out.println(ans);
    }
}