洛谷 P3069 分析（别看）

科技起源

2026-07-09 13:49:52

发布于：河北

1阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值

1.2 题目背景、允许、禁止与限制

背景：有一 $n$ 头奶牛，每头奶牛都有一个编号
允许：最多选出其中的 $k$ 种编号，并把它们从奶牛中剔除。接下来，选一个区间，使得这段区间中全部为相同的编号的奶牛，求这段区间最长能是多长
禁止：
限制：

1.3 题目数据范围与猜测

$1 \le n \le 10^5 \longrightarrow O(n~log~n)$

1.4 一句话概括题意

有一个由多种（也有可能是一种）数字组成的序列 $a$ ，求至多删除 $k$ 种数字后，一段区间内只有一种数字时，所有可能的区间最长是多长

2 题目破题推导

注：以下七种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

正向思维：尝试删除 $k$ 种数字
逆向思维：因为题目中要求“区间”，而“区间”天然就是连续的，因此我们考虑和 $k$ 有关的：题目可以理解成要求至多删除 $k$ 种数字后区间内只剩 $1$ 种数字时的最长区间长度。因此如果一个区间至多有 $k+1$ 种元素，那么这段区间就是合法的
那我们如何找到所有合法的区间呢？这时候就要用到分情况考虑了（看2.3）

2.3 分情况考虑

我们可以尝试从序列的最左边开始，

如果到目前为止这个范围内的数字种类数 $\le k+1$ ，那就不断扩充右区间，直到这个范围内的数字种类数 $>k+1$
然后就需要收缩左区间直到这个范围内的数字种类数 $\le k+1$

2.4 数学

2.5 以终为始、以始为终

2.6 手动推导

2.7 边界测试

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：左端点，右端点，扩充 $\longrightarrow$ $\huge{滑动窗口}$
实施方案：(数组模拟）
记录滑动窗口左端点l，右端点r
记录区间种类数kind和标记数组cnt，用于实时记录某个数字的出现情况
记录最终答案ans，每次到一个合法的区间，就更新答案

while(r <= n){
    // 1. r右移一位，把a[r]放进窗口
    if (++cnt[a[++r]] == 1){
        // 这个血统之前窗口里0头，现在变成1头 → 新增一种血统
        kind++;
    }
    // 2. 如果窗口种类 > k+1，违规，缩左边界l
    while(kind == k + 2){
        if (--cnt[a[l++]] == 0){
            // 删掉a[l]后，这个血统窗口里没了 → 总种类减1
            kind--;
        }
    }
    // 3. 当前窗口合法，更新答案：当前r的奶牛在窗口有多少头
    ans = max(ans, cnt[a[r]]);
}

4 最终代码（禁止抄袭，仅用于参考）

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

int n, k;
map<int, int> cnt; 
const int N = 1e5 + 10;
int a[N];

signed main(){
	
	cin >> n >> k;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
	}
	int l = 1, r = 0;
	int kind = 0, ans = 0;
	while(r <= n){
		if (++cnt[a[++r]] == 1){
			kind++;
		}
		while(kind == k + 2){
			if (--cnt[a[l++]] == 0){
				kind--;
			}
		}
		ans = max(ans, cnt[a[r]]);
	}
	cout << ans;
	return 0;
}