方法思路

这道题目要求我们找到最少操作次数将所有数字染红。操作有两种：一种是单独染色一个白色元素，另一种是选择一个区间染色，要求区间两端元素不同且均为白色。我们需要分析不同情况下的最优解。

1. 首尾元素不同：如果数组的首尾元素不同，可以直接对整个数组进行一次区间染色，操作次数为1。
2. 首尾元素相同，中间存在连续不同的元素：如果存在至少两个连续的元素与首尾元素不同，可以将这些元素分成两个区间染色，操作次数为2。
3. 首尾元素相同，中间无连续不同的元素：此时，所有与首尾不同的元素都是孤立的，即每个不同元素前后都是相同的首尾元素。这种情况下，需要对这些孤立元素单独染色，并选择最小的连续相同元素区间进行染色，操作次数为2加上最小连续相同元素区间的长度。

代码实现

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        // Special case for n=1
        if (n == 1) {
            System.out.println(1);
            return;
        }

        if (a[0] != a[n - 1]) {
            System.out.println(1);
            return;
        }

        boolean hasConsecutiveDiff = false;
        int minConsecutiveSame = n;
        int currentConsecutiveSame = 0;

        for (int i = 1; i < n - 1; i++) {
            if (a[i] != a[0]) {
                if (i + 1 < n - 1 && a[i + 1] != a[0]) {
                    hasConsecutiveDiff = true;
                }
                if (currentConsecutiveSame < minConsecutiveSame) {
                    minConsecutiveSame = currentConsecutiveSame;
                }
                currentConsecutiveSame = 0;
            } else {
                currentConsecutiveSame++;
            }
        }

        if (currentConsecutiveSame < minConsecutiveSame) {
            minConsecutiveSame = currentConsecutiveSame;
        }

        if (hasConsecutiveDiff) {
            System.out.println(2);
        } else {
            System.out.println(2 + minConsecutiveSame);
        }
    }
}

Python

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    a = list(map(int, input[ptr:ptr + n]))
    ptr += n
    
    # Special case for n=1
    if n == 1:
        print(1)
        return

    if a[0] != a[-1]:
        print(1)
        return

    has_consecutive_diff = False
    min_consecutive_same = n
    current_consecutive_same = 0

    for i in range(1, n - 1):
        if a[i] != a[0]:
            if i + 1 < n - 1 and a[i + 1] != a[0]:
                has_consecutive_diff = True
            if current_consecutive_same < min_consecutive_same:
                min_consecutive_same = current_consecutive_same
            current_consecutive_same = 0
        else:
            current_consecutive_same += 1

    if current_consecutive_same < min_consecutive_same:
        min_consecutive_same = current_consecutive_same

    if has_consecutive_diff:
        print(2)
    else:
        print(2 + min_consecutive_same)

if __name__ == "__main__":
    main()

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // Special case for n=1
    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }

    if (a[0] != a[n - 1]) {
        cout << 1 << '\n';
        return 0;
    }

    bool has_consecutive_diff = false;
    int min_consecutive_same = n;
    int current_consecutive_same = 0;

    for (int i = 1; i < n - 1; ++i) {
        if (a[i] != a[0]) {
            if (i + 1 < n - 1 && a[i + 1] != a[0]) {
                has_consecutive_diff = true;
            }
            if (current_consecutive_same < min_consecutive_same) {
                min_consecutive_same = current_consecutive_same;
            }
            current_consecutive_same = 0;
        } else {
            current_consecutive_same++;
        }
    }

    if (current_consecutive_same < min_consecutive_same) {
        min_consecutive_same = current_consecutive_same;
    }

    if (has_consecutive_diff) {
        cout << 2 << '\n';
    } else {
        cout << 2 + min_consecutive_same << '\n';
    }

    return 0;
}