洛谷 P2564 分析（别看）

科技起源的小号1

2026-08-24 20:48:32

发布于：天津

8阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

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

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

背景：
有一个很长的彩带，有 $n$ 个彩珠，它们可以被分成 $k$ 组，分别坐落在彩带的不同位置上
允许：
剪一段彩带，保证这个彩带中含有所有 $k$ 种珠子
求最小彩带的裁剪长度
限制：
可能存在某些坐标并没有珠子
可能存在一个坐标有多颗珠子

1.3 题目数据范围与猜测

$n \le 10^6~~~~~~~~~~1\le k \le 60~~~~~~~~~~0\le珠子位置<2^{31}$

1.4 一句话概括题意

有一个数轴，有若干珠子坐落在上，求分割最短距离使得该范围内包含所有种类的珠子

2 题目破题推导

2.1 第一步：以终为始

以终为始思考：要想使得答案最短，这个区间的样子应为？
先给一个基本猜测：至少存在一个区间，使得该区间左右端点均坐落在彩珠上且 $左 \rightarrow 右$ 这个区间内包含所有种类的彩珠

2.2 第二步：数学推导+证明

假设我们有一个任意合法区间 $[l_0,r_0]$ ， $l_0$ 和 $r_0$ 可以是数轴上的任意实数，满足这个范围内含有全部 $k$ 种彩珠

处理左端点
如果 $l_0$ 本身就在某个彩珠上，记 $l_1 \leftarrow l_0$
如果 $l_0$ 并不在某个彩珠上，找到其右边第一个彩珠的位置，记作 $l_1$
处理右端点
如果 $r_0$ 本身就在某个彩珠上，记 $r_1 \leftarrow r_0$
如果 $r_0$ 并不在某个彩珠上，找到其左边第一个彩珠的位置，记作 $r_1$

原来的彩珠范围内 $[l_0,r_0]$ 内的所有彩珠，一定都留在 $[l_1,r_1]$ 的范围内，因为我们只是调整了空白区域的位置
同时 $r_0-l_0\ge r_1-l_1$ ，所以一定保证这会比原来结果好
那么一旦存在多个结果均比原来结果好，就说明一定存在一个区间使得左右端点在彩珠上且满足截取要求

2.3 第三步：限制

那么我们就把一个数轴上所有实数区间变成若干个区间，这些区间是任意两个点位置的左右端点
这样有左右端点的限制了

3 模型匹配

每个点按位置从左到右排序
然后大概类似一个双指针：head和tail分别都是珠子编号
tail不断++，直到扩展区间能完全包含 $k$ 种珠子，更新答案，然后收缩头部直到区间不能完全包含 $k$ 种珠子

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

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

int n, k;
const int N = 1e6 + 10, M = 66;
int vis[M];
struct node{
    int type;
    int pos;
}a[N], f[N];
bool cmp(node x, node y){
    return x.pos < y.pos;
}

signed main(){

    cin >> n >> k;
    int idx = 0;
    for (int i = 1;i <= k;i++){
        int ti;
        cin >> ti;
        for (int j = 1;j <= ti;j++){
            cin >> a[++idx].pos;
            a[idx].type = i;
        }
    }
    sort(a + 1, a + n + 1, cmp);
    int ans = LLONG_MAX;
    int kind = 0;
    for (int head = 1, tail = 1;tail <= n;tail++){
        if (++vis[a[tail].type] == 1){
            kind++;
        }
        if (kind == k){
            while(kind == k){
                ans = min(ans, a[tail].pos - a[head].pos);
                if (--vis[a[head++].type] == 0){
                    kind--;
                }
            }
        }
    }
    cout << ans;
    
    return 0;
}