链接：https://ac.nowcoder.com/acm/contest/20960/1031
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

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

输入描述: 

	

		第一行包含两个整数N, K，分别表示彩珠的总数以及种类数。
	


	

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

输出描述: 

应包含一行，为最短彩带长度。
示例1

输入 

6 3
1 5
2 1 7
3 1 3 8

输出 

3
本题可以将数据变成一维结构体数组的形式，将pos作为彩球所在的下标，col作为彩球的种类。此时根据pos进行一个排序就可以采用双指针的方式进行计算。
代码： 
//用尺取法试一试，但感觉会超时
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6+10;

struct Node{
    //对应的彩珠种类
    int col;
    //对应的坐标
    int pos;
} a[MAXN];

int vis[66];
int cnt = 0;

bool comp(Node n1, Node n2) {
    if (n1.pos<n2.pos) return true;
    return false;
}

int main() {
    int N, K, T, n=0;
    cin>>N>>K;
    //读入
    for (int i=1;i<=K;i++) {
        cin>>T;
        while (T--) {
            cin>>a[++n].pos;
            a[n].col = i;
        }
    }
    //然后根据坐标进行一个排序
    sort(a+1, a+n+1, comp);
    //进行一个双指针
    int slow=1, fast=1;
    int ans = INT_MAX;
    while (slow<=n&&fast<=n) {
        while (cnt!=K&&slow<=n&&fast<=n) {
            //将该种类的数目增加
            vis[a[fast].col]++;
            if (vis[a[fast].col]==1) {
                cnt++;
            }
            fast++;
        }
        while (cnt==K) {
            ans = min(ans, a[fast-1].pos-a[slow].pos);
            vis[a[slow].col]--;
            if (vis[a[slow].col]==0) {
                cnt--;
            }
            slow++;
        }
    }
    cout<<ans;
    return 0;
}