自动搬运

查看原文

来自洛谷，原作者为

	jjsnam I'm no good at goodbyes.

搬运于2025-08-24 21:49:19，当前版本为作者最后更新于2022-09-26 21:10:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

写在前面

学校的作业。翻了一遍题解区，看不懂或者没有 LaTeX，补一个比较详细的题解。

题目描述（戳这里查看原题）

• 给定一个银行存折，初始存款是 $p$，最终存款是 $q$。

• 给出一个可能错误的账单明细，即由 $n$ 个操作组成的序列，由 +、- 组成。分别表示操作：存 $1$ 块钱，取 $1$ 块钱。

• 两种修改：①对于某个操作符号取反，即 + $\rightarrow$ - 或 - $\rightarrow$ +，代价为 $x$。②将最后一个操作移到操作序列最前端，代价为 $y$。

• 求如何修改使代价最小的同时满足最终存款为 $q$，且任意操作后账户余额不为负数，求出最小代价。

• $n,p,q ≤ 1\times 10^6$，$x,y ≤ 1000$。

正文

乍一看好像是个 DP。但是仔细想想方案数设出来总是在 $O(n^2)$ 左右。所以我们把几个操作分开看，因为互相似乎没有什么影响。

分析

先来看取反操作。如果说对一个操作符取反，那么最终答案会有什么变化？首先，定义 $sum_i$ 表示整个操作从头到 $i$ 位置总的变化量（即前缀和）。容易想到 + 对应 $sum_i=sum_{i-1}+1$，反之同理。那么，如果将一个符号取反，比如 + $\rightarrow$ -，那么对最终 $sum_n$ 的影响是一定的，即 $-2$，反过来就是 $+2$。

再者，移动操作对 $sum_n$ 没有影响。因为旋转不会改变序列中总的操作符数量和种类。那么，为了使 $p+sum_n = q$，我们首先可以确定至少需要取反的操作符个数 $m$，记为代价一。即：

而且注意，这种必要取反操作只会发生在一种操作符。（毕竟如果两种都操作有一些变化能抵消，那就不是最小代价了）

这样我们首先满足了最终存款是 $q$，再来考虑怎么满足任意时刻余额不为负。

数学化的，$\forall i\in[1,n]$，$p+sum_i≥0$。那么，因为有 - 的存在，所有 $sum_i$ 中一定会有一个最小值，我们可以找出这个最小值 $sum_i$。可能 $p+sum_i<0$，考虑什么操作可以让 $p+sum_i$ 变大。一种是通过移动操作，通过移动一些操作符，让更多的 + 到前面，使所有 $sum_i$ 尽可能的大。还有一种操作，就是“交换”，即在操作序列后部让一个 + $\rightarrow$ -，在前部让一个 - $\rightarrow$ +，这样 $sum_n$ 不会改变，但是最小的 $sum_i$ 就会变大。

接下来想一想最终答案怎么求。

移动操作不好确定，我们尝试 $O(n)$ 枚举移动了几个操作符，那么就钦定了所有移动情况，此时的基础移动代价记作代价二。假设移动了 $k$ 个操作符：

我们定义 $Min[k]$ 表示钦定移动了 $n-k$ 个操作符，此时序列末尾是原来的 $k$ 时的操作序列，最小的 $sum_i$。那么先把至少要改的操作符改掉。这里要贪心的想，为了让 $p+sum_i$ 尽可能大，如果是 - $\rightarrow$ +，这种变化更靠前是最好的，这样能使 $p+sum_i$ 变大；如果是 + $\rightarrow$ - 则越靠后越好，这样对 $p+sum_i$ 不会产生负影响。（先假定这样，证明会在后文提及）我们加入对 $p+sum_i$ 的影响，记作 $temp$。那么如果此时仍然有 $temp < 0$。就只能通过刚才定义的“交换操作”让 $temp$ 变大（注意一次“交换操作”的代价是 $2x$）。

细节与实现

其实刚才的很多做法都是我们猜的，我们尝试证明一下，这也是这道题的难点。

1. 上文中必要的取反操作，贪心选取 + $\rightarrow$ - 时越靠后越好，因为对 $p+sum_i$ 无影响，为什么？

   我们考虑一下如果有影响会是什么情况。比如这样 ---+-，如果按照贪心思路把这个 + 变成 -，那 $p+sum_i$ 不就更小了吗？

   其实不然。如果出现这种情况，证明后面已经没有可以选择的 + 了，那么此时因为有影响，$i$ 变成 $n$，即更改完 $q=p+sum_n<0$。在题目保证有解的条件下这种情况不合法。因此不会有这种有影响的事情发生。

2. 必要的取反操作在 - $\rightarrow$ + 时为什么能全部贡献给 $sum_i$？

   也不一定是全部。如果此时 $i$ 前面的 - 很多，那么一定能全部贡献给 $sum_i$。如果比较少，那么不用全部贡献就能使 $p+sum_i≥0$ 了，而且也不必进行后面的操作。所以计算影响的时候都视作全部贡献对最终答案是不会有影响的。

3. 为什么只用考虑操作序列中最小的 $sum_i$？是否存在 $j$，使 $j≠i$ 且 $p+sum_j<0$？

   存在的。但是，在我们处理 $sum_i$ 时，一定也可以顺便把 $sum_j$ 都处理了。两种情况：

   • 若 $j>i$。那么我们通过处理让 $p+sum_i≥0$。根据定义 $sum_i≤sum_j$，由前缀和性质前面增加的量会传递到后面，则 $p+sum_j≥0$。
   • 若 $j<i$。如果更改的符号在 $[1,j]$，则一定能同时让 $sum_j$ 和 $sum_i$ 增加。因为 $sum_i≤sum_j$，因此满足 $p+sum_j≥0$ 的时刻一定不晚于 $p+sum_i≥0$。如果更改的符号在 $(j,i]$，但这是不可能的。因为根据贪心思想，此时出现的情况一定是如 ----++，且不能通过取反操作完成 - $\rightarrow$ +，则只能通过交换操作变成+----+ 这样，则又可以回到前一种情况。

4. 交换操作为什么一定可行？是否会因为交换导致出现一个新的最小值 $sum_j$？

   不会。根据我们交换操作时的贪心，选取尽可能靠后的 + 变成 -，尽可能前的 - 变成 +。如果出现了新的 $sum_j$，那只有可能是 +++-...---，那此时 $j$ 又变成了 $n$，根据证明 1 这种情况也不可能出现。

这样我们刚才思路里所有可能出锅的点都证明完了，所以这个思路是没有问题的。接下来看看具体实现。

1. 如何求出每一种移动情况下的 $Min[i]$？

   其实这个移动操作很明显的有一种绕环转的意味，而且是反着转。那么我们按照套路将原序列倍长，同样前缀和也倍长，就可以求出每一个 $Min[i]$ 了。比如当 $i=n$ 时我们应该在 $[n+1,n+n]$ 里取最小值；这样当 $i=1$ 时就可以在 $[2,n+1]$ 里决策，不会 RE。下面是化简过的式子：

   $$Min[i]=\min_{i<j≤i+n}(sum_j)-sum_i$$

   观察这个式子，明显是 RMQ 问题。可以用线段树，当然 $10^6$ 有点悬。注意到决策区间是连续的，类似滑动窗口，故可以使用单调队列。

2. 交换操作的具体代价是什么？

   交换操作是两次取反，一次在 $sum_i$ 的 $i$ 前，一次在后。前面那个对 $sum_i$ 有影响，后面的无。那么根据一次 - $\rightarrow$ + 的变化是 $+2$，只需要 $\lceil\dfrac{\left|p+sum_i\right|}{2}\rceil$ 次交换操作就能是剩下的 $p+sum_i≥0$。记为代价三：

   $$Cost3=2\times x\times\lceil\dfrac{ \left|p+sum_i\right|}{2}\rceil\ \ \ (p+sum_i < 0) $$

最后每种情况的总代价就是上述三个代价和。

$O(n)$ 单调队列预处理所有 $Min[i]$，$O(n)$ 枚举所有移动情况，每种情况的代价都可以 $O(1)$ 求出。最终的总时间复杂度是 $O(n)$。

代码

最终的代码比较短。变量名和函数功能见注释。
要注意的是文章中为了便于理解用的 $sum_i$ 来表示 $Min[i]$。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int maxn = 1000006;

int Min[maxn];
int sum[maxn << 1];
int n, p, q, x, y;

int abs(int x){//绝对值函数
    return x > 0 ? x : -x;
}

void init(){
    /* 处理前缀和 */
    for (int i = 1; i <= n << 1; i ++){
        sum[i] += sum[i - 1];
    }

    /* 单调队列求 Min[i] */
    int q[maxn << 1], hh = 0, tt = -1;
    for (int i = n, j = n << 1; i > 0; i --){
        while (hh <= tt && q[hh] > i + n) hh ++;
        while (j > i){
            while (hh <= tt && sum[q[tt]] >= sum[j]) tt --;
            q[++ tt] = j --;
        }
        Min[i] = sum[q[hh]] - sum[i];
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> p >> q >> x >> y;
    char op;
    for (int i = 1; i <= n; i ++){
        cin >> op;
        sum[i] = sum[i + n] = (op == '+' ? 1 : -1);
    }

    init();
    int m = (q - (p + sum[n])) >> 1;//至少要取反的操作符数量

    int ans = 0x7fffffff;
    for (int i = n; i > 0; i --){
        int cost = abs(m) * x + (n - i) * y; // 代价1 + 代价2
        int temp = p + Min[i];
        if (m > 0){//对temp能有贡献
            temp += m << 1;
        }
        if (temp < 0){//需要交换操作
            cost += 2 * x * ((abs(temp) + 1) / 2);// 代价3
        }
        ans = min(ans, cost);
    }

    cout << ans << endl;

    return 0;
}

总结

一开始看到单调队列就往 DP 想了，但是我们要知道的是单调队列的本质是数据结构，所以不仅仅只有优化 DP 一种功能，和贪心结合也是很常见的。

本题的难点不在单调队列，在于复杂的贪心能否想出来以及对于不确定的思路敢不敢继续深入，最后能否对不确定的思路都证明正确性。

谢谢观看！