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


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

大家有好的做法嘛？



提问于10天前
10011


3 个问答


1

显然单调队列

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

1

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

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

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

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

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

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

0

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

回答于10天前
19873
@Siriuss:  好了。 –  Siriuss   10天前
呃，我是看了没思路，回来凭着记忆写出来的，我重新描述一下呢。 –  Siriuss   10天前
我来回答