题解 LGP8537 「Wdoi-2」花如幻想一般

赛时竟然想了好久，后来开窍了，$O(n)$ 的做法，dalao 勿喷。

思路

分 $2$ 种情况：翻转 $1$ 次的和没翻转的（如果翻 $2$ 次就没意义了）

① 没翻转的

每次操作可以给任意一朵花加上或减去任意的美丽程度，所以一朵花只调整一次即可，否则就浪费次数了。

也就是说，遍历两个序列时，如果对应值不同，操作总数 $+ 1$。

② 翻转 $1$ 次的

即翻转后当做没翻转的情况来计算次数，最后再 $+ 1$。

代码

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int a[500005], b[500005];

void reverseA()//将a序列倒过来
{
    for (int i = 1, j = n; i < j; i++, j--)
        swap(a[i], a[j]);
}

int cal()//计算现在的序列只加减美丽程度，需要操作多少次
{
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        cnt += (a[i] != b[i]);//如果两个不一样，即++
    /*
    也可改为：
        if (a[i] != b[i])
            cnt++;
    */
    return cnt;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    int ans = cal();//不翻转的情况
    reverseA();//如果翻转
    ans = min(ans, cal() + 1);//和翻转的情况取最小即可，记得+1
    cout << ans << endl;
    return 0;
}

---

• 分类： OI 题解
• 标签： 无标签