标签: 双指针

[SCOI2009]生日礼物 题解

[SCOI2009]生日礼物 题解

题目地址:洛谷:【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<231

题解

本题可以用一个叫做“双指针”的算法解决。我们将珠子按照它们的坐标排序后,固定这个序列的左端(左指针),寻找一个最近的右端位置(右指针)使得左端到右端之间包含了所有颜色的珠子。由于有左右两个指针,我们把这种算法叫做双指针。具体而言,我们可以用一个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;
}