_旋转の题解_

经验分享区
1

思路

很显然的一道贪心

我们可以先看一下样例是怎么来的：我们可以先将两个数组相减：

得到 -1 -1 0 3 3, 当然因为只能逆时针旋转，我们需要把数组转化成 3 3 0 3 3 也就是将负数 + 4, 容易发现我们可以在左边3 3 的地方使用一次魔法， 右边 3 3 的地方使用一次魔法，把他们变成 0，得到这个 3 3 0 3 3 数组的时候，我们可以使用一个差分数组得到答案 3 0 -3 3 0

得到这个差分数组之后我们就很好做了，对于不同的值，我们进行分类讨论：

  1. d[i] >= -1，此时d[i] += 4后，至少贡献 3 的答案，因为d[j]最大是3，所以无论如何不会减少答案。
  2. d[i] = -2，此时d[i]变成2后，贡献2的答案，d[j]必须是3，才能减少1的答案。
  3. d[i] = -3，此时d[i]变成1后，贡献1的答案，d[j] = 2可以减少1的答案，d[j] = 3可以减少2的答案

对于以上的分类讨论，容易得到以下做法：我们从左往右扫d[i]，碰到-2或者-3就累计入计数器。碰到-1,0就什么都不做。碰到1就累计1的答案。碰到2，我们要找找前面有没有-3，如果有的话可以把-3用掉，减少1的答案。碰到3，我们优先用-3（减少2的答案），如果没有-3，可以用-2（减少1的答案）。很容易证明，优先用-3再用-2的策略是正确的。复杂度 O(n)

其实没有什么代码难度(前提是你推出了以上所有内容)

核心 code

for_(i, 1, n)
{
    if (d[i] == -2)
    {
        cnt2++;
    }
    else if (d[i] == -3)
    {
        cnt1++;
    }
    else if (d[i] == 1)
    {
        ans++;
    }
    else if (d[i] == 2)
    {
        if (cnt1 > 0)
        {
            cnt1--;
            ans += 1;
        }
        else
        {
            ans += 2;
        }
    }
    else if (d[i] == 3)
    {
        if (cnt1 > 0)
        {
            cnt1--;
            ans += 1;
        }
        else if (cnt2 > 0)
        {
            cnt2--;
            ans += 2;
        }
        else
        {
            ans += 3;
        }
    }
}