生日礼物

Posted on Edited on In

题目大意:将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上.为了让礼物彩带足够漂亮，希望这一段彩带中能包含所有种类的彩珠,彩带尽可能短(彩带的长度即为彩带开始位置到结束位置的位置差)求最短彩带长度.

用队列来维护.

几乎是一眼题目.实在没有什么思维量,碰到新的就压入,判断是否已经齐全了,然后就不断弹弹弹.

小细节:统计答案的时候,不是r-l,而是q[r].id - q[l].id

比如只有两个珠子1,2,但是他们分别在下标10,100处,如果统计r-l则是1,但是若统计下标的话则为90.天壤之别!

代码如下:

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
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 1e6 + 66;

int n, k, col, cnt, l, r;
int mp[66], res(12345678910);

struct yhzhyhm
{
    int id, val;
    bool operator < (const yhzhyhm &x) const {return id < x.id;}
}yh[N], q[N];

signed main()
{
    int i, x, y;
    n = read(), k = read();
    for (i = 1; i <= k; ++ i)
    {
        x = read();
        while (x --) y = read(), yh[++ cnt].id = y, yh[cnt].val = i;
    }
    sort(yh + 1, yh + 1 + n);

    for (i = 1; i <= n; ++ i)
    {
        q[++ r] = yh[i], ++ mp[yh[i].val];
        if (mp[yh[i].val] == 1) ++ col;
        while (col == k)
        {
            res = min(res, q[r].id - q[l].id);
            -- mp[yh[l].val];
            if (! mp[yh[l].val]) -- col;
            ++ l;
        }
    }
    put(res);
    return 0;
}

后记:

细节决定成败