题目地址：洛谷：【P2564】[SCOI2009]生日礼物 – 洛谷、BZOJ：Problem 1293. — [SCOI2009]生日礼物

题目描述

小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。
小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？彩带的长度即为彩带开始位置到结束位置的位置差。

题意简述

有K种颜色的珠子共N个，分别在一长段彩带的不同位置，可能存在多个珠子在同一位置的情况，求最短的子彩带使得彩带上具有所有K种颜色的珠子，长度定义为终止坐标-起始坐标。

输入输出格式

输入格式：
第一行包含两个整数N, K，分别表示彩珠的总数以及种类数。接下来K行，每行第一个数为Ti，表示第i种彩珠的数目。接下来按升序给出Ti个非负整数，为这Ti个彩珠分别出现的位置。

输出格式：
输出应包含一行，为最短彩带长度。

输入输出样例

输入样例#1：

6 3
1 5
2 1 7
3 1 3 8

输出样例#1：

3

说明

【样例说明】
有多种方案可选，其中比较短的是1~5和5~8。后者长度为3最短。
【数据规模】
对于50%的数据， N≤10000；
对于80%的数据， N≤800000；
对于100%的数据，1≤N≤1000000，1≤K≤60，0≤Ti<2³¹。

题解

本题可以用一个叫做“双指针”的算法解决。我们将珠子按照它们的坐标排序后，固定这个序列的左端（左指针），寻找一个最近的右端位置（右指针）使得左端到右端之间包含了所有颜色的珠子。由于有左右两个指针，我们把这种算法叫做双指针。具体而言，我们可以用一个cnt数组维护指针之间的区间内每种颜色珠子的数量，如果归0就对种类数-1，如果从0变为非0就对种类数+1。那么我们只需要让左指针左移时减去上一个位置的珠子，然后再寻找右指针的位置，这样维护一通，并且对每一对左右指针求长度更新答案即可。
排序采用STL排序，复杂度O(n \log n)，根据上面的描述，双指针算法是O(n)的，因此总复杂度O(n \log n)，可以通过本题。
双指针是常用的基础算法，常常能在CF题中见到它。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>
#include <utility>

typedef long long LL;
typedef std::pair<int, int> PII;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1000005;

int n, k, cnt[MAXN];
std::vector<PII> vec;

int main() {
    n = readint(); k = readint();
    for(int i = 1, ti, pos; i <= k; i++) {
        ti = readint();
        while(ti--) {
            pos = readint();
            vec.push_back(PII(pos, i));
        }
    }
    std::sort(vec.begin(), vec.end());
    int ans = 1e9, sum = 0;
    int r = 0;
    for(int l = 0; l < vec.size(); l++) {
        while(r < vec.size() && sum < k) {
            if(!cnt[vec[r].second]) sum++;
            cnt[vec[r].second]++;
            r++;
        }
        if(r >= vec.size() && sum < k) break;
        ans = std::min(ans, vec[r - 1].first - vec[l].first);
        cnt[vec[l].second]--;
        if(!cnt[vec[l].second]) sum--;
    }
    printf("%d", ans);
    return 0;
}