[SCOI2009] 生日礼物

[题目链接]

         https://www.lydsy.com/JudgeOnline/problem.php?id=1293

[算法]

         首先将所有礼物按x坐标为关键字排序

         然后 ， 用Two-Pointers计算答案即可

         时间复杂度 : O(NlogN)

[代码]

        

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
const int MAXK = 65;
const int inf = 2e9;

struct info
{
        int x , type;
} a[MAXN];

int n , k , len;
int s[MAXK];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
    T f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    x *= f;
}
inline bool cmp(info a , info b)
{
        return a.x < b.x;
}

int main()
{
        
        read(n); read(k);
        for (int i = 1; i <= k; i++)
        {
                int t;
                read(t);
                for (int j = 1; j <= t; j++)
                {
                        read(a[++len].x);
                        a[len].type = i;        
                }        
        }
        sort(a + 1 , a + n + 1 , cmp);
        int cnt = 0 , ans = inf , head = 1;
        for (int i = 1; i <= n; i++)
        {
                ++s[a[i].type];
                if (s[a[i].type] == 1) ++cnt;
                while (head < i && s[a[head].type] > 1) --s[a[head++].type];
                if (cnt == k) chkmin(ans , a[i].x - a[head].x);    
        }
        printf("%d
" , ans);
        
        return 0;
    
}