【每日一题】9月15日题目精讲

题号 NC110615
名称 Present
来源 CF460C
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

看到最小值最大——二分
对于任何一个数字我们都需要将它加到大于等于ans，所以，从左往右扫描，对于每一个小于ans的值都将以他为左界的区间加上若干个1直到它等于ans，这个区间加操作可以用线段树等维护，也可以使用差分——虽然这里的操作不是离线的，但是每次修改的都是后面的区间，而每个点的值只会被之前的点修改到，所有我们可以保证对每个元素的求值都是在之前的所有区间修改之后的。（这里提醒大家思考时间轴的概念，对于修改查询类问题，能不能离线取决于操作与时间是否有关，也就是说时间轴这一维度的影响是什么样子在，我们不离线的时候其实是默认时间轴存在的，但是事实上，这一维未必需要存在，或者就像本题一样，因为贪心策略是找到当前需要变大的最左边的点修改它和他右边的区间，于是就导致了时间维和我们从左到右枚举的坐标轴其实就是一个维度）。

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目9月22日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴