| ||||||||||
| 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