1293: [SCOI2009]生日礼物

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 1096  Solved: 584

[ ][ ]

Description

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

Input

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

Output

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

Sample Input

6 3
1 5
2 1 7
3 1 3 8

Sample Output

3

HINT

有多种方案可选，其中比较短的是1~5和5~8。后者长度为3最短。

【数据规模】

对于50%的数据， N≤10000；

对于80%的数据， N≤800000；

对于100%的数据，1≤N≤1000000，1≤K≤60，0≤彩珠位置<2^31。

Source

 

 题解：这个嘛，终于没有脑抽啦（phile：好评如潮 HansBug：么么哒）。。。思路也比较简单，就是直接通过那个啥的各个柱子（HansBug：啊呸，珠子 phile：你啊一看就是被Aruba多了。。。 HansBug：TT这都被你发现了）的坐标从小到大排个序，然后先从1开始找一段最短的可满足题意的子段，记录下长度，然后把这个子段第一个位置的各个珠子全部扔掉，再在结尾处往下扩充，每次都尽可能少的扩充但是要满足扩充后能包含M种珠子，然后每次记录下当前段的长度，这样子滚过去一边就可以啦，理论复杂度为O(nlogn+n)（PS：1.提醒一下，注意彩珠位置可以是0，所以在排序的数组中建议存储时+1，反正不影响结果，而且后续处理时少不少麻烦 2.这题居然3928ms我也是醉了，估计这个序列比较有序，所以快排比较逗比么么哒）

 

  1 var

 2    i,j,k,l,m,n,ll:longint;

 3    a,b,c:

array[

0..

1000500] 

of longint;

 4 

procedure swap(

var x,y:longint);

 5           

var z:longint;

 6           

begin

 7                z:=x;x:=y;y:=z;

 8           

end;

 9 

procedure sort(l,r:longint);

10           

var i,j,x,y:longint;

11           

begin

12                i:=l;j:=r;x:=a[(i+j) 

div 

2];

13                

repeat

14                      

while a[i]<x 

do inc(i);

15                      

while a[j]>x 

do dec(j);

16                      

if i<=j 

then

17                         

begin

18                              swap(a[i],a[j]);

19                              swap(b[i],b[j]);

20                              inc(i);dec(j);

21                         

end;

22                

until i>j;

23                

if i<r 

then sort(i,r);

24                

if l<j 

then sort(l,j);

25           

end;

26 

begin

27      readln(n,m);

28      fillchar(a,sizeof(a),

0);

29      fillchar(b,sizeof(b),

0);

30      

for i:=

1 

to m 

do

31          

begin

32               read(l);

33               

for j:=

1 

to l 

do

34                   

begin

35                        read(k);

36                        inc(a[

0]);a[a[

0]]:=k+

1;

37                        b[a[

0]]:=i;

38                   

end;

39               readln;

40          

end;

41      a[

0]:=

0;l:=

0;

42      sort(

1,n);

43      fillchar(c,sizeof(c),

0);

44      i:=

1;

45      j:=

1;

46      

while (l<m) 

and (j<=n) 

do

47            

begin

48                 k:=j;

49                 

while a[j]=a[k] 

do

50                       

begin

51                            inc(c[b[j]]);

52                            

if c[b[j]]=

1 

then inc(l);

53                            inc(j);

54                       

end;

55            

end;

56      

if j>n 

then halt;

57      ll:=a[j-

1]-a[i];

58      

while j<=n 

do

59            

begin

60                 k:=i;

61                 

while a[i]=a[k] 

do

62                       

begin

63                            dec(c[b[i]]);

64                            

if c[b[i]]=

0 

then dec(l);

65                            inc(i);

66                       

end;

67                 

while (l<m) 

and (j<=n) 

do

68                       

begin

69                            k:=j;

70                            

while (l<m) 

and (a[j]=a[k]) 

do

71                                  

begin

72                                       inc(c[b[j]]);

73                                       

if c[b[j]]=

1 

then inc(l);

74                                       inc(j);

75                                  

end;

76                       

end;

77                 

if l<m 

then break;

78                 

if (a[j-

1]-a[i])<ll 

then ll:=a[j-

1]-a[i];

79            

end;

80      writeln(ll);

81 

end.