洛谷 P1094 纪念品分组

P1094 纪念品分组

先按价格对纪念品排序（这里是从大到小），然后从两端向中心开始配对，有两个变量i和j，表示正在处理的两个纪念品编号，开始时i=1，j=n，如果a[i]+a[j]>w则第i贵的纪念品无法与任何较小的纪念品配对，那么该纪念品单独一组，i++，否则第i贵的纪念品可以和第j便宜的纪念品一组，因此i++,j--，两种情况都使ans++，而i=j时说明纪念品分组完成，于是退出。

var a:array[1..30010] of integer;

i,w,n,t,x,ans,j:longint;    boo:boolean;

procedure qsort(l,r:longint);{从大到小排序}

var i,j,k,temp:longint;

begin

  i:=l;

  j:=r;

  k:=a[(i+j) div 2];

  repeat

    while a[i]>k do inc(i);

    while a[j]<k do dec(j);

    if i<=j

      then

      begin

        temp:=a[i];

        a[i]:=a[j];

        a[j]:=temp;

        inc(i);

        dec(j);

      end;

  until i>j;

  if i<r then qsort(i,r);

  if j>l then qsort(l,j);

end;

begin

  readln(w);

  readln(n);

  for i:=1 to n do

    readln(a[i]);

  qsort(1,n);

  i:=1;j:=n;

  while i<=j do

  begin

    inc(ans);

    if i=j then break;

    if a[i]+a[j]<=w

      then dec(j);

    inc(i);

  end;

  writeln(ans);

end.