Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
思路特别二笔……但是试了几个数据都对,然后WAA,为毛啊type kind=record l,w:longint; end; arr=array[1..10000]of longint; var i,n,cas:longint; a:array[1..10000]of kind; procedure init(); var i:longint; begin readln(n); for i:=1 to n do read(a[i].l,a[i].w); // readln; end; procedure qsort(l,r:longint); var i,j,x,y:longint;t:kind; begin i:=l;j:=r; x:=a[(l+r)div 2].l; y:=a[(l+r)div 2].w; repeat while(a[i].l<x)or((a[i].l=x)and(a[i].w<y))do inc(i); while(a[j].l>x)or((a[j].l=x)and(a[j].w>y))do dec(j); if i<=j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; inc(i);dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end; procedure work(); var ans,i,j,t,q:longint; b:arr;f:boolean; begin t:=0;ans:=1;q:=a[1].w; for i:=2 to n do begin if a[i].w<q then begin if t=0 then begin inc(ans); inc(t);b[t]:=a[i].w; end else begin f:=true; for j:=1 to t do if b[j]<a[i].w then begin f:=false;break; end; if f then begin inc(ans); inc(t);b[t]:=a[i].w; end; end; end else q:=a[i].w; end; writeln(ans); end; begin readln(cas); while cas>0 do begin init;qsort(1,n); // for i:=1 to n do writeln(a[i].l,' ',a[i].w); work(); dec(cas); end; end. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator