POJ1083 Moving Tables--heap+욕심--pku1083

가장 간단한 구간은 욕심이지만 고찰은 세심하다.
참고 사항:
1、s>t의 상황을 고려
2. 읽을 때 s, t를 각각 (s+1)div2와 (t+1)div2로 변환해야 한다.
코드:

Program poj1083;//By_Thispoet

Const 

	maxn=200;

Var

	t,i,j,k,m,n						:Longint;

	heap,l,r						:Array[1..maxn*2]of Longint;

	heap_size						:Longint;

	

Procedure Down(i:Longint);

var j:Longint;

begin

	while ((i<<1)<=heap_size) do 

		begin

			j:=i<<1;

			if (j<heap_size)and(heap[j]>heap[j+1])then inc(j);

			if heap[j]<heap[i] then 

				begin

					heap[i]:=heap[i] xor heap[j];

					heap[j]:=heap[i] xor heap[j];

					heap[i]:=heap[i] xor heap[j];

					i:=j;

				end else break;

		end;

end;

	

	

Procedure Up(i:Longint);

var j:Longint;

begin

	while (i>1) do 

		begin

			j:=i>>1;

			if heap[j]>heap[i] then 

				begin

					heap[i]:=heap[i] xor heap[j];

					heap[j]:=heap[i] xor heap[j];

					heap[i]:=heap[i] xor heap[j];

					i:=j;

				end else break;

		end;

end;

	

	

Procedure Qsort(ll,rr:Longint);

var i,j,k,temp:Longint;

begin	

	i:=ll;j:=rr;

	k:=l[i+random(j-i+1)];

	repeat

		while l[i]<k do inc(i);

		while l[j]>k do dec(j);

		if i<=j then 

			begin

				temp:=l[i];l[i]:=l[j];l[j]:=temp;

				temp:=r[i];r[i]:=r[j];r[j]:=temp;

				inc(i);dec(j);

			end;

	until i>j;

	if ll<j then Qsort(ll,j);

	if i<rr then Qsort(i,rr);

end;

	

	

Procedure Swap(var i,j:Longint);

begin

	i:=i xor j;

	j:=i xor j;

	i:=i xor j;

end;

	

	

BEGIN	



	readln(t);

	randomize;

	

	while t>0 do 

		begin

		

			heap_size:=0;

			readln(n);

			for i:=1 to n do 

				begin

					readln(l[i],r[i]);

					if l[i]>r[i] then Swap(l[i],r[i]);

					l[i]:=(l[i]+1)>>1;

					r[i]:=(r[i]+1)>>1;

				end;



			Qsort(1,n);

			for i:=1 to n do 

				begin

					if (heap_size>0)and(heap[1]<l[i])then 

						begin

							heap[1]:=r[i];

							Down(1);

						end else 	

							begin

								inc(heap_size);

								heap[heap_size]:=r[i];

								Up(heap_size);

							end;

				end;

			writeln(heap_size*10);

			dec(t);

			

		end;



END.