题解：CF2033C Sakurako's Field Trip

题目链接

• 洛谷 CF2033C Sakurako's Field Trip

解题思路

因为可以随便转换，所以每对点的交换是对其他点对没有任何影响的。

所以考虑贪心，对于每个点对想办法减少代价。

设两个点分别为 $i,j$（$i+j-1=n$）,

故一定产生代价的情况可以分成以下四种：

1. $a_i=a_j$ 且 $a_i=a_{i+1}$ 或 $a_i=a_{j-1}$（产生 $1$ 的代价）

2. $a_i=a_j=a_{i+1}=a_{j-1}$（产生 $2$ 的代价）

3. $a_{i+1}=a_{j-1}$ 且 $a_i=a_{i+1}$ 或 $a_j=a_{i+1}$（产生 $1$ 的代价）

最后特判中间两个人会不会产生代价，这道题就这么做完了~

参考代码

#include <bits/stdc++.h>
#define N 200005
using namespace std;

int T , n , a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while(T--)
    {
        cin >> n;
        for(int i = 1 ; i <= n ; i++)
        {
            cin >> a[i];
        }
        int ans = 0;
        for(int i = 1 ; i <= (n - 1) / 2 ; i++)
        {//第二种情况会被前后各判一次，故不需要特判
            if(a[i + 1] == a[n - i])
            {
                if(a[i] == a[i + 1] || a[n - i + 1] == a[i + 1])
                {
                    ans++;
                }
            }
            if(a[i] == a[n - i + 1])
            {
                if(a[i] == a[i + 1] || a[i] == a[n - i])
                {
                    ans++;
                }
            }
        }
        if(n % 2 == 0 && a[n / 2] == a[n / 2 + 1])
        {
            ans++;
        }
        cout << ans << endl;
    }
    return 0;
}