首页 > 试题广场 >

移山

[编程题]移山
  • 热度指数：1171 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
天帝被愚公的诚心感动，命令手下的仙人帮助移山。
然而仙人的法术也是有局限性的，山势连绵起伏，法术并不能直接把山移走。每次施法，可以把一段连续区域的山头移走相同高度。现在愚公想知道什么时候会有至少一个山头高度小于等于0
给出一个长度为 n 的数组 a_1,a_2,...,a_n ，和 m 表示山头的高度和可以施法的次数，每次施法还会给出左右端点 L,R 和高度 h，表示将 a_L,...a_R 依次减去 h。问在哪次操作之后存在一个 a_i \leq 0？（数据保证这样的时刻存在。）

输入描述:
第一行两个数 n 和 m，表示山头数量和施法次数。
第二行n个数，分别表示a_1,a_2,...,a_n ，即第一个山头到第n 个山头的高度。
接下来m行，每行三个数L,R,h，表示一次施法的具体参数。

1 \leq n,m \leq 10^5, 1 \leq h, a_i \leq 10^9, 1 \leq L\leq R \leq n，均为整数


输出描述:
输出一个整数，表示答案。数据保证答案存在。
示例1

输入

5 4
6 5 3 4 6
1 3 2
4 4 2
3 5 1
1 5 6

输出

3

说明

第一次操作之后山头变成4 3 1 4 6
第二次操作之后山头变成4 3 1 2 6
第三次操作之后山头变成4 3 0 1 5
其中第三个山头高度小于等于了0，可见，在第三次施法之后有一个山头的高度变成了0
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-11 18:26:04
题目链接 REAL776 移山 题目描述 给出 座山和它们的高度 。总共有 次移山操作。每次操作会指定一个连续的区间 和一个高度 ，将这个区间内所有山的高度都减去 。 问题是，在哪一次操作之后，首次出现至少一个山头的高度小于等于 0？题目保证答案一定存在。 解题思路 1. 核心观察：单调性 这 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

线段树 小米集团
难度：
7条回答 349浏览

热门推荐

相关试题

移山

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号