P3470题解

jjsnam · 2022-09-26 21:10:51 · 题解

写在前面

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

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

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

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

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

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

正文

乍一看好像是个 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)

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