思路

  此题是一个贪心加双指针的问题，可以对任意位置进行染色，所以我们可以对每一种颜色来单独看待，对于每一种颜色我们记录这一种颜色所出现的所有的位置，若我们想要得到最长的连续，最优的一定是利用染色去“连接”记录位置中每一段，即去填补两段相同颜色之间的空缺，填补完后剩下的次数不足以补足即可以接在最长的段两旁，所以对于每一种颜色我们可以用双指针枚举要填补的所有空缺段后最长段的左右节点，之所以可以用双指针枚举，因为对于有限染色次数，当固定一个端点后另一端点的位置是符合单调性的

代码

c++

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

int cal(vector<int> a, int k, int n) {
    int l = 0, cnt = 0, res = 0;
    for (int r = 0; r < a.size(); r++) {
        if (r != 0) {
            cnt += a[r] - a[r - 1] - 1;
        }
        while (cnt > k) {
            cnt -= a[l + 1] - a[l] - 1;
            l += 1;
        }
        res = max(res, a[r] - a[l] + 1 + k - cnt);
    }
    return min(n, res);
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> idx(m + 1);
    vector<int> v(n);

    for (int i = 0; i < n; i++) {
        cin >> v[i];
        idx[v[i]].push_back(i);
    }

    int ans = k;
    for (auto id : idx) {
        ans = max(ans, cal(id, k, n));
    }

    cout << ans << endl;

    return 0;
}

java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static int cal(List<Integer> a, int k, int n) {
        int l = 0, cnt = 0, res = 0;
        for (int r = 0; r < a.size(); r++) {
            if (r != 0) {
                cnt += a.get(r) - a.get(r - 1) - 1;
            }
            while (cnt > k) {
                cnt -= a.get(l + 1) - a.get(l) - 1;
                l += 1;
            }
            res = Math.max(res, a.get(r) - a.get(l) + 1 + k - cnt);
        }
        return Math.min(n, res);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();

        List<List<Integer>> idx = new ArrayList<>();
        for (int i = 0; i <= m; i++) {
            idx.add(new ArrayList<>());
        }

        List<Integer> v = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int value = scanner.nextInt();
            v.add(value);
            idx.get(value).add(i);
        }

        int ans = k;
        for (List<Integer> id : idx) {
            ans = Math.max(ans, cal(id, k, n));
        }

        System.out.println(ans);

        scanner.close();
    }
}

python

def cal(a, k, n):
    l, cnt, res = 0, 0, 0
    for r in range(len(a)):
        if r != 0:
            cnt += a[r] - a[r - 1] - 1
        while cnt > k:
            cnt -= a[l + 1] - a[l] - 1
            l += 1
        res = max(res, a[r] - a[l] + 1 + k - cnt)
    return min(n, res)

n, m, k = map(int, input().split())
idx = [[] for _ in range(m+1)]
v = list(map(int, input().split()))
for i in range(n):
    idx[v[i]].append(i)

ans = k
for id_ in idx:
    ans = max(ans, cal(id_, k, n))

print(ans)

题目内容

小明很喜欢给玻璃珠染成不同的颜色，他现在有一排$N$个玻璃珠，第$i$个玻璃珠的颜色是$c_i$，他现在有$M$种颜色，他希望找到最长的一串颜色相同的玻璃珠(一串表示下标是连续的)，他现在有$K$次操作可以把$K$个位置的玻璃珠染成任意的颜色。

小明想知道，经过最多$K$次操作之后，它可以得到的最长的一串颜色相同的玻璃珠是多长?

注意:你最多对$K$个位置染色，你也可以选择不染色。

输入描述

第一行三个数$N,M,K(1≤N,M≤2×10^5,0≤K≤N)$分别表示玻璃球的数量，玻璃球的颜色以及操作的最多次数。

第二行$N$个数，$c_i(1≤c_i≤M)$表示小明还没有染色之前玻璃珠的颜色,

输出描述

输出一个值$sum$表示小明可以得到的最长的一串玻璃珠。

样例1

输入

5 5 1
1 2 1 3 3

输出

3

说明

把$2$位置的颜色改成$1$，或者把$3$位置的颜色变成$3$都可以得到长度为$3$的答案。

样例2

输入

4 4 0
1 2 3 4

输出

1

说明

不能修改颜色，所以答案是$1$。