小O的数组染色

[题目链接](https://www.nowcoder.com/practice/1e20b2f3daa14e8389c847eab1ab1f64)

题意

给定长为 的数组 ，初始全为白色。每次操作选择区间 ，要求 ，将该区间内所有元素染红。求将所有元素染红的最小操作次数。

思路

问题转化

每次操作覆盖一个区间 ，约束为 （特别地， 时 恒成立，即单个元素可以一次操作单独染色）。目标是用最少的区间覆盖 。

这是一个经典的贪心区间覆盖问题。

关键观察

对于每个位置 作为左端点，能覆盖的最远右端点是 ，即值 在数组中最后一次出现的位置。

证明：选择 ，，则 ，区间合法，覆盖范围为 。不可能有比 更远的右端点（以 为左端点时），因为更远处不存在值等于 的元素。

贪心算法

预处理前缀最大覆盖：

$$

表示"从位置 1 出发，通过某个左端点 的操作，最远能覆盖到哪里"。

贪心过程：

1. 当前已覆盖到位置 （初始 ）。
2. 选择左端点 的最优操作，右端点为 。
3. 操作数加 1，令 。
4. 重复直到 。

时间复杂度：（预处理 last 和 maxReach 各 ，贪心 ）。

样例验证

样例1：

• ：，，
• ：

贪心：

• ，，操作数 = 1，
• ，，操作数 = 2，

输出 2 ✓

样例2：

• ：，，
• ：

贪心：

• ，到达 1，操作数 = 1，
• ，到达 2，操作数 = 2，
• ，到达 3，操作数 = 3，

输出 3 ✓（每个元素值唯一，只能单独染色）

代码

C++

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

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n+1);
        for (int i = 1; i <= n; i++) cin >> a[i];

        map<int, int> last;
        for (int i = 1; i <= n; i++) last[a[i]] = i;

        vector<int> maxReach(n+1);
        maxReach[1] = last[a[1]];
        for (int i = 2; i <= n; i++) {
            maxReach[i] = max(maxReach[i-1], last[a[i]]);
        }

        int ops = 0, cur = 1;
        while (cur <= n) {
            ops++;
            cur = maxReach[cur] + 1;
        }
        cout << ops << "\n";
    }
    return 0;
}

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));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] a = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }

            Map<Integer, Integer> last = new HashMap<>();
            for (int i = 1; i <= n; i++) last.put(a[i], i);

            int[] maxReach = new int[n + 1];
            maxReach[1] = last.get(a[1]);
            for (int i = 2; i <= n; i++) {
                maxReach[i] = Math.max(maxReach[i-1], last.get(a[i]));
            }

            int ops = 0, cur = 1;
            while (cur <= n) {
                ops++;
                cur = maxReach[cur] + 1;
            }
            sb.append(ops).append("\n");
        }
        System.out.print(sb);
    }
}