[SCOI2009] 生日礼物

发表于 | 分类于 >
字数统计 : 375   |   阅读时长 ≈ 2 mins.

题目

链接

[SCOI2009]生日礼物

题意简述

有一条纸带上挂着 $n \ (n <= 1000000)$ 个小球，小球有 $k \ (k <= 60)$ 种颜色。
s
找出一个最小的包含所有颜色的区间。

思路

单调队列

使一个队列中一直保持有所有颜色，不断向右移动
若末尾小球的颜色出现次数 $ > 1$ ，将其弹出，直到末尾小球的颜色出现次数 $ = 1$ 。
时间复杂度： $O(n)$ 。

代码

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
48
49
50
51
52
53
54
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 1e6 + 10, kmax_int = 2147483647, kmod = 1e9+7;

int n, k;

#define pii std::pair<int, int>
#define mp std::make_pair

pii point[kmax_num];
int col[61];

std::deque<pii>	queue;

inline bool Check()	{
    For(i,1,k)	if(!col[i])	return 1;
    return 0;
}

int main() {
    std::cin >> n >> k;
    REG int sum, pos, cnt = -1;
    For(i,1,k)	{
        std::cin >> sum;
        FOR(h,0,sum)	{
            std::cin >> pos;
            point[++cnt] = mp(pos, i);
        }
    }
    std::sort(point, point + n);

    cnt = 0;
    while(Check())	{
        queue.push_front(point[cnt]);
        ++col[point[cnt].second];
        ++cnt;
    }

    REG int ans = 0x7fffffff;
    while(cnt < n)	{
        ans = std::min(ans, queue.front().first - queue.back().first);
        queue.push_front(point[cnt]);
        ++col[point[cnt].second];
        while(col[queue.back().second] > 1)
            --col[queue.back().second], queue.pop_back();
        ++cnt;
    }
    ans = std::min(ans, queue.front().first - queue.back().first);
    printf("%d\n", ans);
    return 0;
}

杂项

  • 这里用了 $std::pair$ 实现，$std::pair$ 大法好！