一道没思路的题，大佬请进。


2


我昨天看到一道题，没有什么好的思路，所以求助一下大家

N个非负数，每次找到M个(不足m个连续的区间不能删除)连续非负的区间将他们减去1，求若干次操作之后总和最小值多少？
输入N, M:
样例1:
5 3
2 1 5 3 2
输出： 4

样例1说明：
先将 1 5 3 区间减少 1, 样例变为2 0 4 2 2
然后将 4 2 2 区间减少2，样例变为2 0 2 0 0, 答案为4

样例2：
5 3
5 5 5 0 5
输出：5

样例1说明：
将 5 5 5 区间减去5，答案为5

数据范围: 1 <= N <= 500000, 1 <= M <= N

大家有好的做法嘛？



提问于2022-09-17 09:17
22397


4 个问答


1

显然单调队列

回答于2022-09-17 10:06
94731
@Aigrl:  已经点赞啦 –  Siriuss   2022-09-17 10:48
@Siriuss:  记得点赞同啊qwq –  Aigrl   2022-09-17 10:40
@Aigrl:  ok，懂了 –  Siriuss   2022-09-17 10:39
@Aigrl:  最小值不是答案是可以减的值，后效性处理麻烦了点 –  Aigrl   2022-09-17 10:24
@Siriuss:  你得先明白操作顺序不影响最终答案，然后贪心构造不就行了。 –  Aigrl   2022-09-17 10:23
@Aigrl:  呃，可是这道题不是求剩下的所有元素之和最小嘛。 –  Siriuss   2022-09-17 10:22
@Siriuss:  后效性可以类似处理 –  Aigrl   2022-09-17 10:18
@Siriuss:  https://www.luogu.com.cn/problem/P8102 –  Aigrl   2022-09-17 10:17
@Siriuss:  维护区间最小值 –  Aigrl   2022-09-17 10:14
怎么单调队列呀。 –  Siriuss   2022-09-17 10:09

1

感觉像贪心，从区间左端的长度为 M 的区间开减，减不了了，找下一个继续

感觉可以这么证明：
我们的贪心方案每次减的区间都是当前能减的区间中最靠左的
如果最优解的方案与贪心解的不同，从左到右找到第一个不同的减去区间或数值

最优解的区间和贪心解相同，只是减去的数小了 k（不可能减的比贪心解多）
这是因为贪心解的当前区间的右边一部分区间在最优解中被下一个区间减去了k，这时可以把最优解下一个区间的减去操作少减去k，改到当前贪心解的区间减去，总减去值不变，就把当前最优解转化成了贪心解

最优解区间和贪心解区间有一部分重合，方案分别是
贪心区间在左减去t * M，最优区间在右减去k * M（这是最靠左的最优区间）
t 大于 k，最优区间直接不减了，全挪到贪心区间去减，当前最优解转化成了贪心解
t 小于 k，最优区间挪 t * M 给贪心区间减去，凑出贪心解
从左到右依次执行这样最优解就能转化成贪心解

就像样例1那样
最优解153减1，变成贪心解215减1

回答于2022-09-17 10:00
30788
@4_3:  点赞！ –  Siriuss   2022-09-17 11:36
@Siriuss:  写详细了点儿，就是把最优解拆开凑出了当前的贪心解，再依次去找下一个不同的地方，最后把所有最优解变成贪心解 –  4_3   2022-09-17 11:25
@4_3:  有一部分重合那里感觉有点问题，贪心区间没办法再减去了呀，这两个区间都只能减去重合区间的最小值，所有减去的k是一样的。 –  Siriuss   2022-09-17 11:10
@Siriuss:  补了个证明，我感觉还可以 –  4_3   2022-09-17 10:56
@4_3:  有道理，从左删和从右删是等效的，他都是删除了同样数量的值。 –  Siriuss   2022-09-17 10:25
@Siriuss:  我感觉没啥区别，对于一个区间的最小值，不管在哪个区间被减去，都是减去它的高度或者那个区间的最小值的高度 –  4_3   2022-09-17 10:20
我也只想到贪心，但是感觉不太对。如果一个区间大于m，可以先减前面或者先减后面，效果不太一样。 –  Siriuss   2022-09-17 10:08

0

从题目中可以知道三个结论：
1. 如果序列无限长，并且这个序列是单调递增的，那么一定可以让序列都变成 0
2. 现在序列有长度限制，假设在某一次修改中，对于一个数 a[i]
｜i 前面第一个 0 的位置 - i 后面第一个 0 的位置｜ < m，那么 a[i] 怎么也不可能变成 0
3. 进一步 a[i] 可以变成 0 的充要条件是
(i 前面第一个 < a[i] 的位置) 减去 (i 后面第一个 < a[i] 的位置) 的绝对值 < m

我的想法是可以用如下算法

  1. 用线段树维护序列，同时维护 minv（区间最小值），sum（区间和）

  2. i = 1 to n 扫描这个序列，线段树二分找到 [i, i+m-1] 区间内第一个 < a[i] 的位置 p
    （如果左子树区间 minv 都比 a[i] 大，就去右子树找，否则就去左子树）

  3. 如果找不到？那么单点修改，a[i] -> 0，并且 i = i+1

  4. 找到了这个位置 p？ 区间修改，[i, i+m-1] 区间 都减去 minv
    并且让 i = p+1，继续

  5. 最后，线段树根节点的sum就是答案

回答于3个月前
174042

0

感觉题目描述的不是很清楚，。，，你自己出题吗？

回答于2022-09-17 09:36
28319
@Siriuss:  好了。 –  Siriuss   2022-09-17 09:58
呃，我是看了没思路，回来凭着记忆写出来的，我重新描述一下呢。 –  Siriuss   2022-09-17 09:53
我来回答