[SCOI2009]生日礼物

题目背景

四川2009NOI省选

题目描述

小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。

小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？彩带的长度即为彩带开始位置到结束位置的位置差。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

1
2
3
4
6 3
1 5
2 1 7
3 1 3 8

样例输出 #1

1
3

提示

【样例说明】

有多种方案可选，其中比较短的是1~5和5~8。后者长度为3最短。

【数据规模】

对于50%的数据， N≤10000；

对于80%的数据， N≤800000；

对于100%的数据，1≤N≤1000000，1≤K≤60，$0≤$珠子位置$<2^{31}$。

$\sum T_i =n$

题解

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <queue>
#include <algorithm>
#define RI register int
#define OffCinCout std::ios::sync_with_stdio(false)
#define OffBindIO std::cin.tie(0)

using namespace std;

struct L{
    int no,x;
}p[1000010];

int cmp(L l1,L l2){
    return l1.x<l2.x;
}

int main(){
    OffCinCout;
    OffBindIO;
    queue<L> q;
    int N,K,t,cunt=0,cnt[70]{};
    cin >> N >> K;
    for(RI i=1;i<=K;i++){
        cin >> t;
        for(RI j=1;j<=t;j++){
            cin >> p[++cunt].x;
            p[cunt].no = i;
        }
    }
    sort(p+1,p+1+N,cmp);
    int flag=0,ans=0x3f3f3f3f;
    for(RI i=1;i<=N;i++){
        if(cnt[p[i].no] == 0) ++flag;
        ++cnt[p[i].no];
        q.push(p[i]);
        while(!q.empty()&&cnt[q.front().no]>1){
            cnt[q.front().no]--;
            q.pop();
        }
        if(flag == K){
            ans = min(ans,p[i].x-q.front().x);
        }
    }
    cout << ans << "\n";
    return 0;
}

思路

用尺举法的一个队列解法，研究了好长时间终于会了，其过程是由右指针不断右移，然后不断维护cnt数组，判断队首的元素的序号出现次数，如果多了就pop掉，如果少了就不管。最后不断维护ans就能得出答案。

这题卡了n多时间，菜菜、捞捞。