[ARC136C] Circular Addition 题解

braveTester · 2023-10-19 22:09:23 · 题解

题意

给一个有 1 \le n \le 2\times 10^5 个元素的环，初始为全 0。每次可以在环上选取一个长度在 [1, n] 的区间，使得每个元素都加一。

问达到目标状态 A 所需要的最小操作步数。

题解

这里给出和官方题解不一样的一种思路。

断环成链

直觉上，如果这个问题可以断环成链，那么就会和 [NOIP2013 提高组] 积木大赛类似，因此首先尝试是否可以寻找到一些特殊点并从此处断开。

对于涉及某一个特定元素的操作，可以将其上的操作分成以下几类：

环；
仅从此元素开始；
仅在此元素终止；
既在此元素开始又在此元素终止（仅选该元素进行操作）；
既不在此元素开始又不在此元素终止（穿过该元素）；

注：如果一个操作是环，会归类到环上；其他操作才会归类到剩余的类别中。

容易观察到，如果对于位置 i 和 i + 1，有操作 O_1 在 i + 1 上开始（1，4），有操作 O_2 在 i 上终止（3，4），那么可以将操作 O_1 和 O_2 拼接在一起，如果长度溢出的话就再拆出另一个操作，这样做不会使得操作数增加。

由此可以得到以下两个推论：

如果 i + 1 处有操作的起始，那么 i 不会有操作的终止；
如果 i 处有操作的终止，那么 i + 1 处不会有操作的起始。

利用以上两个推论，可以发现一定存在一个最优解，其在最小值处只会有两种操作：环（1），或者穿过（5）。

为了证明这个发现，需要一些细节上的讨论。由于这些细节易于理解，但是在此说明过于冗长，因此略去。

环与穿过的区分

断环成链以后（令最小值为第一个元素，即 A[0]），按照 [NOIP2013 提高组] 积木大赛的思路，有以下贪心策略：对于位置 i + 1，其会尽量白嫖 i 上的操作，实在不行再新开。初始时默认已有 A[0] 个操作，不需要付出代价。

但是这样会有一个问题：对于 0 上的穿过操作，会正确的计算代价，但是对于环操作，却会漏掉代价，最后需要加上。但是我们无法区分 0 上有多少穿过和环。

注意到，虽然我们无法区分穿过和环，但是对于上述的贪心策略是没有任何影响的，因此我们只需要在此基础上最小化环的数量即可。

第一个尝试是直接最小化环的数量，即一旦有操作消失，先让从 0 开始的操作消失，尝试构造穿过操作，这样环的数量最小。然而这种方式会有反例，例如对于 1 2，会发现实际构造的操作只有一个长度为 3 的操作，违反了长度限制。

分析发现，原因在于虽然试图让操作尽早结束以构造穿过操作，但是只关注了穿过的结束，实际上并没有那么多合法的穿过起始位置。

为了解决这个问题，将一个元素上的操作分成三个集合：

从 0 起始的操作；
有潜力构成穿过的操作；
其他操作。

根据贪心策略，

如果 A[i] < A[i + 1]，那么会有 A[i + 1] - A[i] 个操作出现。这些操作都可以尝试构成穿过的起始位置，但是和已有的有潜力构成穿过的操作数量之和不可以超过已经消失的从 0 起始的操作。其余都是其他操作；
如果 A[i] > A[i + 1]，那么会有 A[i] - A[i + 1] 个操作消失。根据我们的目标，我们希望优先让从 0 起始的操作消失，这样可以让后面出现更多有潜力的操作；同时让有潜力的操作最后消失，这样可以使环最少。

最终贪心的代价加上 A[0] 再减去在 A[n - 1] 有潜力构成穿过的操作数目即可。

实际应该是消失的从 0 起始的操作数目和有潜力构成穿过的操作数目取 \min，不过由于上述计算过程，有潜力的穿过数目一定小于等于消失的从 0 起始的操作数目，因此化简为上式。

代码

#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int NMAX = 2 * 210000;
const int INF = ~0u>>2;

int N;
int A[NMAX];
long long ans = 0;

void try_subtract(int &x, int &delta)
{
    int tmp = min(x, delta);
    x -= tmp;
    delta -= tmp;
}

void try_add(int &x, int &delta, int limit)
{
    int tmp = min(limit - x, delta);
    x += tmp;
    delta -= tmp;
}

int main()
{
    scanf("%d", &N);
    int min_val = INF;
    int m_pos = 0;
    for(int i = 0;i < N;i += 1)
    {
        scanf("%d", &A[i]);
        A[i + N] = A[i];
        if(min_val > A[i])
        {
            min_val = A[i];
            m_pos = i;
        }
    }
    ans = 0;
    int left = A[m_pos];
    int x = A[m_pos], y = 0, z = 0;
    // x: 从 0 起始的操作
    // y: 其他操作
    // z: 有潜力构成穿过的操作
    for(int i = 0;i < N;i += 1)
    {
        int idx = m_pos + i;
        ans += max(A[idx] - left, 0);
        if(A[idx] < left) {
            int delta = left - A[idx];
            try_subtract(x, delta);
            try_subtract(y, delta);
            try_subtract(z, delta);
        } else {
            int delta = A[idx] - left;
            try_add(z, delta, A[m_pos] - x);
            try_add(y, delta, INF);
        }
        left = A[idx];
    }
    // A[m_pos + N - 1] 到 A[m_pos] 的转移不必做，不影响 z
    ans += A[m_pos] - z;
    printf("%lld\n", ans);
    exit(0);
}