bzoj 1293: [SCOI2009]生日礼物

 1 #include <queue>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <functional>
 6 using namespace std;
 7 #define N 1000008
 8 #define K 68
 9 
10 int n,k,ans = 2147483647;
11 
12 priority_queue<int,vector<int>,greater<int> > que[K];
13 
14 void init()
15 {
16     scanf("%d%d",&n,&k);
17     for (int i = 1;i <= k;i++)
18     {
19         int num,a;
20         scanf("%d",&num);
21         while (num--)
22         {
23             scanf("%d",&a);
24             que[i].push(a);
25             que[0].push(a);
26         }
27     }
28 }
29 
30 void debug()
31 {
32     for (int i = 1;i <= k;i++)
33     {
34         while (!que[i].empty())
35         {
36             printf("%d ",que[i].top());
37             que[i].pop();
38         }
39         printf("\n");
40     }
41 }
42 
43 void work()
44 {
45     while (!que[0].empty())
46     {
47         int u = que[0].top(),m = 0;
48         for (int i = 1;i <= k;i++)
49         {
50             while (que[i].top() < u && !que[i].empty()) que[i].pop();
51             if (que[i].empty()) return ;
52             m = max(m,que[i].top() - u);
53         }
54         ans = min(m,ans);
55         que[0].pop();
56     }
57 }
58 
59 int main()
60 {
61     init();
62 //    debug();
63     work();
64     printf("%d\n",ans);
65     return 0;
66 }