花如幻想一般

chen_zhe · 2022-09-10 20:54:25 · 题解

首先可以证明，翻转操作不会执行超过 1 次，这是因为翻转两次就相当于把数列给翻转回来，没有进行任何操作了。

因此可以分类讨论，讨论当不进行翻转操作和进行一次翻转操作的情况。假设一次翻转操作都不进行，也就是只执行加法操作，那么就是对照一下有哪些对应位数字不一样即可。进行一次翻转操作也是同理的，先将数列翻转过来再对照一下有哪些对应位数字不一样。两者的操作次数取最小值即可。

参考代码如下：

#include <iostream>

using namespace std;

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

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 cnt1=0,cnt2=1;
    for (int i=1;i<=n;i++)
    {
        if (a[i]!=b[i])
            cnt1++;
    }
    for (int i=n;i>=1;i--)
    {
        if (a[n-i+1]!=b[i])
            cnt2++;
    }
    cout << min(cnt1,cnt2) << endl;
    return 0;
}