Description

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

Input

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

Output

应包含一行, 为最短彩带长度.

Sample Input

6 3
1 5
2 1 7
3 1 3 8

Sample Output

3

Data Range

对于 50% 的数据,\(N \leq 10000\)

对于 80% 的数据,\(N \leq 800000\)

对于 100% 的数据,\(1 \leq N \leq 1000000, 1 \leq K \leq 60, 0 \leq T_i \lt 2^{31}\)

Explanation

这道题有一点单调的意思

黄学长的做法是建立一个类似单调队列的东西, 方法如下:


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 1000005, maxm = 65;
const int infinit = 0x7fffffff;

int n, ncnt, K;
int head[maxm], next[maxn], // Chain requires those.
    val[maxn], arr[maxn]; // Values
int res = infinit;

bool judge(int x)
{
    int maxx = 0;
    // Iterate through colours
    for (int i = 1; i <= K; i++) {
        // Iterating link, until a result was found
        while (val[head[i]] > x) {
            if (!next[head[i]])
                return false;
            head[i] = next[head[i]];
        }
        if (val[head[i]] <= x)
            maxx = max(maxx, x - val[head[i]]);
    }
    res = min(res, maxx);
    return true;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &K);
    res = infinit;
    for (int i = 1, x; i <= K; i++) {
        scanf("%d", &x);
        for (int j = 1, y; j <= x; j++) {
            scanf("%d", &y);
            val[++ncnt] = y;
            next[ncnt] = head[i];
            head[i] = ncnt;
            arr[ncnt] = y;
        }
    }
    sort(arr + 1, arr + 1 + ncnt);
    for (int i = ncnt; i >= 1; i--) {
        if (arr[i] != arr[i + 1])
            if (!judge(arr[i]))
                break;
    }
    printf("%d\n", res);
    return 0;
}

最开始我的想法是贪心爬虫 (毛毛虫, 不停往前吃, 然后如果尾巴过长, 就是如果缩回还可以继续满足条件, 那么就缩尾巴. 即便如此毛毛虫总是在往前吃的)

但是为什么写不过呢? 后来 pyjudge 了一发才发现问题出在 res 的 max 值上了. max 其实 是远大于 \(N\) 的, 所以应该设成 infinity...... 这样交了就可以 AC 了

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 1001000, maxk = 64;
const int infinit = 0x7fffffff;

struct bead { int pos, typ; };
bool operator < (bead a, bead b) {
    return a.pos < b.pos; }

int n, K, acnt;
int status[maxk];
bead arr[maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= K; i++) {
        int sz; scanf("%d", &sz);
        for (int j = 1, x; j <= sz; j++) {
            scanf("%d", &x);
            arr[++acnt].pos = x;
            arr[acnt].typ = i;
        }
    }
    sort(arr + 1, arr + 1 + n);
    // Done sorting, crawling for result
    memset(status, 0, sizeof(status));
    int avail = 0; // Fulfilled type of beads
    int begin = 1; // Beginning of this bead
    int res = infinit;
    for (int i = 1; i <= n; i++) {
        // Inserting new bead into current place.
        int typ = arr[i].typ;
        if (status[typ] <= 0)
            avail += 1;
        status[typ] += 1;
        // printf("avail %d -> %d %d %d\n", avail, status[1], status[2], status[3]);
        // Removing beads, until finally appropriate
        while (begin < i && status[arr[begin].typ] > 1) {
            status[arr[begin].typ] -= 1;
            begin += 1;
        }
        if (avail >= K)
            res = min(res, arr[i].pos - arr[begin].pos);
        continue;
    }
    printf("%d\n", res);
    return 0;
}