学步园

【题意】

有c(c<=100000)头奶牛，现要招收n(n是奇数,n<=19999)头奶牛上大学，给定每头奶牛的智商和所需补助，并给定最大可提供补助和f(f<=2*10^9)，

求补助奶牛的智商最大中位数

【输入】

第一行n、c、f

接下来c行每行两个数字，分别为智商和所需补助

【输出】

一个数字，表示补助奶牛的智商最大中位数

若不存在补助方案则输出-1

不错的题

很容易想到将奶牛按智商从小到大排序，然后枚举中位数

那么问题就是如何确定中位数左右分别选取n div 2头奶牛的最小费用

这个可以通过堆预处理得出

正向扫描一遍每次看当前奶牛所需费用是否小于堆顶元素费用，若小于队顶出堆，当前奶牛费用入堆

反向同理

然后枚举一下中位数即可

program poj2010;
var
  n,c,f,i,j,k,ans,tot:longint;
  heap,cast,cost,suma,sumb:array [0..100001] of longint;

procedure swap (var a,b:longint);
var
  i:longint;
begin
  i:=a;
  a:=b;
  b:=i;
end;

procedure qsort(s,e:longint);
var
  i,j,k:longint;
begin
  if s>=e then exit;
  i:=s;
  j:=e;
  k:=cast[(s+e) div 2];
  while i<=j do
    begin
      while cast[i]<k do inc(i);
      while cast[j]>k do dec(j);
      if i>j then break;
      swap(cast[i],cast[j]);
      swap(cost[i],cost[j]);
      inc(i);
      dec(j);
    end;
  qsort(s,j);
  qsort(i,e);
end;

procedure insert (p:longint);
var
  i:longint;
begin
  inc(tot);
  heap[tot]:=p;
  heap[tot*2]:=-1;
  heap[tot*2+1]:=-1;
  i:=tot;
  while (i<>1)and(heap[i]>heap[i div 2]) do
    begin
      swap(heap[i],heap[i div 2]);
      i:=i div 2;
    end;
end;

procedure delete ;
var
  i:longint;
begin
  if tot=1 then
    begin
      dec(tot);
      exit;
    end;
  swap(heap[tot],heap[1]);
  heap[tot]:=-1;
  dec(tot);
  i:=1;
  while (heap[i]<heap[i*2])or(heap[i]<heap[i*2+1]) do
    if heap[i*2]>heap[i*2+1] then
      begin
        swap(heap[i],heap[i*2]);
        i:=i*2;
      end
                             else
      begin
        swap(heap[i],heap[i*2+1]);
        i:=i*2+1;
      end;
end;

begin
  while not seekeof do
    begin
      read(n,c,f);
      for i:=1 to c do
        read(cast[i],cost[i]);
      qsort(1,c);
      ans:=-1;
      tot:=0;
      heap[1]:=-1;
      for i:=1 to n div 2 do
        begin
          suma[n div 2]:=suma[n div 2]+cost[i];
          insert(cost[i]);
        end;
      for i:=n div 2 + 1 to c do
        if heap[1]>cost[i] then
          begin
            suma[i]:=suma[i-1]-heap[1]+cost[i];
            delete;
            insert(cost[i]);
          end
                           else
          suma[i]:=suma[i-1];
      tot:=0;
      heap[1]:=-1;
      for i:=c downto c - n div 2 + 1 do
        begin
          sumb[c - n div 2 + 1]:=sumb[c - n div 2 + 1]+cost[i];
          insert(cost[i]);
        end;
      for i:=c - n div 2 downto 1 do
        if heap[1]>cost[i] then
            begin
            sumb[i]:=sumb[i+1]-heap[1]+cost[i];
            delete;
            insert(cost[i]);
          end
                           else
          sumb[i]:=sumb[i+1];
      for i:=c - n div 2 downto n div 2 + 1 do
        if cost[i]+suma[i-1]+sumb[i+1]<=f then
          begin
            ans:=cast[i];
            break;
          end;
      writeln(ans);
    end;
end.