1293: [SCOI2009]生日礼物

昨天想了好久这个题，最后发现竟然已经AC过了，还是寒假AC的！！真是。。。。。。

网上都是些动归，堆什么的解法，我是队列。

按位置排序，依次加入队列。加入一个元素后判断，保证队首颜色只有一种。

RunID	User	Problem	Result	Memory	Time	Language	Code_Length	Submit_Time
346220	lbz007	1293	Accepted	15852 kb	3424 ms	Pascal/Edit	1221 B	2013-02-05 18:33:29

View Code

 1 var
 2   ss,c,a,q:Array[0..1000002]of longint;
 3   ans,num,k,n,m,s,x,h,t,i,j:longint;
 4 procedure sort(l,r:longint);
 5   var i,j,x,y:longint;
 6   begin
 7   i:=l;j:=r;
 8   x:=a[(l+r) shr 1];
 9   repeat
10     while a[i]<x do
11       inc(i);
12     while x<a[j] do
13       dec(j);
14     if not(i>j) then
15       begin
16       y:=a[i];
17       a[i]:=a[j];
18       a[j]:=y;
19       y:=c[i];
20       c[i]:=c[j];
21       c[j]:=y;
22       inc(i);dec(j);
23       end;
24     until i>j;
25     if l<j then
26       sort(l,j);
27     if i<r then
28       sort(i,r);
29     end;
30 begin
31   readln(n,k);
32   for i:=1 to k do
33     begin
34     read(x);
35     for j:=1 to x do
36       begin
37       inc(s);
38       c[s]:=i;
39       read(a[s]);
40       end;
41     readln;
42     end;
43   sort(1,n);
44   h:=1;t:=1;
45   inc(ss[c[1]]);
46   num:=1;
47   m:=1;
48   ans:=maxlongint;
49   while t<n do
50     begin
51     inc(t);
52     inc(ss[c[t]]);
53     if (ss[c[t]]=1)and(m<>k) then inc(m);
54     while ss[c[h]]>1 do
55       begin
56       inc(h); dec(ss[c[h-1]]);
57       end;
58     num:=a[t]-a[h];
59     if (num<ans)and(m=k) then
60       ans:=num;
61     end;
62   writeln(ans);
63   end.