1 条题解
-
-9
题目大意就是要在排好序的数组中找出两段总和最大的不重合的区间,并使两个区间中的最大值与最小值的差不超过k。
提示
我们从最左端和最右端开始分别做两次双指针,分别记录两端的最大值,从最左端开始扫记录每一个点的左端最大的差小于等于 k 的序列,而从最右端开始扫则记录的是每一个点的右端最大的差小于等于 k 的序列。这样处理之后,在一遍枚举所有的点,对他两端的状态进行求和,得到的便是最终的答案,即 ans=max(ans,ansl(i)+ansr(i+1)) ,在这之中为了避免重复计算一个点的值,我们所以计算ansl[i] 和 ansr[i+1]
- 1
信息
- ID
- 634
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 102
- 已通过
- 34
- 上传者