Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

思路特别二笔……但是试了几个数据都对,然后WAA,为毛啊

Posted by 1007816143 at 2015-07-17 19:12:41 on Problem 1065
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator