题目大意

给定一个数组 a。进行至多一次操作，使得 a 数组中所有元素相同。如果代价为改变元素数量，求最小代价。

思路

非常简单的贪心，对于每次修改的区间 ai∼aja_i \sim a_j，可以分为以下三种情况：

  • 如果 a1≠ana_1 \neq a_n，那么要修改的区间一定包括这两个点之一，我们只需要选择连续区间长度最长的即可。
  • 如果 a1=ana_1 = a_n，那么我们只要修改除了两端连续区间的所有点。

单词询问时间复杂度为 O(n)O(n)。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve()
{
    int res1 = 1, res2 = 1;
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
        
    for (int i = 2; i <= n; i ++)
    {
        if (a[i] == a[i - 1]) res1 ++;
        else break;
    }
    for (int i = n - 1; i >= 1; i --)
    {
        if (a[i] == a[i + 1]) res2 ++;
        else break;
    }
    
    if (a[1] == a[n])
        cout << max(n - res1 - res2, 0) << '\n';
    else 
        cout << n - max(res1, res2) << '\n';
}