有一个圆上有n个点，有m个要求，分别是(a,b)表示a与b要联通，每个点只能和它左右的点连线，问最少连多少个线段（相邻两点之间连的一条线算1条线段）。
最多要连n-1条线，整个圆上的点都联通，所以枚举不连哪一条线段，算出此时最小的线段数即可。算的时候用next[i]记录i点向后连边的终点，求和的时候就能很快了。
View Code 1 { $inline on} 2 program pku1944(input,output); 3 type 4 node = record 5 x,y : integer; 6 end; 7 var 8 n,p : integer; 9 answer : integer; 10 a : array[0..10001] of node; 11 next : array[0..1001] of integer; 12 procedure swap(var aa,bb: integer ); inline; 13 var 14 t : integer; 15 begin 16 t:=aa; 17 aa:=bb; 18 bb:=t; 19 end; { swap } 20 procedure init; inline; 21 var 22 i : integer; 23 begin 24 readln(n,p); 25 for i:=1 to p do 26 begin 27 readln(a[i].x,a[i].y); 28 if a[i].x>a[i].y then 29 swap(a[i].x,a[i].y); 30 end; 31 end; { init } 32 procedure sort(p,q :longint ); inline; 33 var 34 i,j,m1,m2 : integer; 35 begin 36 i:=p; 37 j:=q; 38 m1:=a[(i+j)>>1].x; 39 m2:=a[(i+j)>>1].y; 40 repeat 41 while (a[i].x m1)or((a[j].x=m1)and(a[j].y>m2)) do 44 dec(j); 45 if i<=j then 46 begin 47 swap(a[i].x,a[j].x); 48 swap(a[i].y,a[j].y); 49 inc(i); 50 dec(j); 51 end; 52 until i>j; 53 if i p then sort(p,j); 55 end; { sort } 56 procedure main; inline; 57 var 58 i,j : integer; 59 xx,yy : integer; 60 sum : integer; 61 begin 62 answer:=maxint; 63 for i:=1 to n do 64 begin 65 sum:=0; 66 fillchar(next,sizeof(next),0); 67 for j:=1 to p do 68 if (a[j].x =i) then 69 begin 70 if a[j].x>next[1] then 71 next[1]:=a[j].x; 72 if next[a[j].y] 0 then 82 begin 83 xx:=j; 84 yy:=next[j]; 85 break; 86 end; 87 inc(sum,yy-xx); 88 for j:=xx+1 to n do 89 begin 90 if next[j]=0 then 91 continue; 92 if j>yy then 93 begin 94 inc(sum,next[j]-j); 95 xx:=j; 96 yy:=next[j]; 97 end 98 else 99 if next[j]>yy then 100 begin 101 inc(sum,next[j]-yy); 102 xx:=j; 103 yy:=next[j]; 104 end; 105 end; 106 if sum