题目链接
塔子哥的法术降峰-小米2023笔试(codefun2000)
题目内容
塔子哥有一项特殊技能，可以降低连绵山峰的高度。每次施法，他能够选定一段连续的山峰区域，使得这些山峰的高度均匀降低。现在他想知道，通过有限次施法之后，何时能使得至少有一个山峰的高度降至海平面以下（高度小于等于 0）。已知山峰的数量和施法的次数，请计算出何时可以实现目标。
输入描述
第一行包含两个正整数 n 和 m，分别表示山峰的数量和施法的次数。
第二行包含 n 个正整数 H1 ,H2,…,Hn，表示每个山峰的初始高度。
接下来的 m 行，每行包含三个正整数 Li ,Ri ,hi ，表示每次施法作用的山峰区间 [Li,Ri] 和降低的高度 hi 。
对于 1 ≤ n , m ≤ 1 0 5 ， 1 ≤ h i , H i ≤ 1 0 9 ， 1 ≤ L i ≤ R i ≤ n 1≤n,m≤10^5 ，1≤hi,Hi≤10^9，1≤Li≤Ri≤n 1≤n,m≤105，1≤hi,Hi≤109，1≤Li≤Ri≤n的输入数据，保证有解。
输出描述
输出一个整数，表示在第几次施法之后，至少有一个山峰的高度降至海平面以下。
样例1
输入
5 4
6 5 3 4 6
1 3 2
4 4 2
3 5 1
1 5 6
输出
3
题解1
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;int n, m, H[N], HH[N], L[N], R[N], h[N], sub[N];bool check(int x){memset(sub, 0, sizeof sub);for(int i = 1; i <= n; i++) HH[i] = H[i];for(int i = 1; i <= x; i++){sub[L[i]] -= h[i]; // 使用差分 sub[R[i] + 1] += h[i];}for(int i = 1; i <= n; i++){sub[i] += sub[i - 1];HH[i] += sub[i]; // 使用前缀和 if(HH[i] <= 0) return true; }return false;
}
int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &H[i]);for(int i = 1; i <= m; i++) scanf("%d%d%d", &L[i], &R[i], &h[i]);int left = 0, right = n+1, mid;while(left + 1 < right){mid = (left + right)/2;if(check(mid)) right = mid;else left = mid;}printf("%d\n", right);return 0;
}