SSL JudgeOnline 1868——谁是组长

Description

SSL中学信息组需要选一个组长。信息组一共有n个人，分别用1到n编号，其中m个人参与了投票。得票数过半（票数大于m div 2）的人将被选为组长。
输入数据将告知这m个人分别将票投给了谁，请统计出谁将担任SSL中学信息组的组长。

Input

第一行两个数n和m。
第二行有m个数，这些数都是不超过n的正整数，表明这m个人的选择。

Output

输出将被选为组长的人。如果没有人的票数过半，请输出-1。

Sample Input

7 4
7 7 2 7
Sample Output

7
Hint

数据规模
1<=n<=maxlongint
1<=m<=10000

---

首先，我们可以用快排将选择的人从小到大排序（便于对后面的搜索，如果直接用数组可能会爆）。

然后我们将这些数据，逐个找他的票数（因为前面已经排序过，所以数据都在一起，只要加几个判断即可）

如找到票数过半就直接输出，退出程序。

---

代码如下：

var
  a:array[0..10000] of longint;
  m,n,i,j:longint;
  f:boolean;

procedure qsort(l,r:longint);
  var
    i,j,k:longint;
  begin
    if l>=r then exit;
    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
          a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];
          inc(i);dec(j);
        end;
    until i>j;
    qsort(i,r);
    qsort(l,j);
end;

begin
  readln(m,n);
  for i:=1 to n do
    read(a[i]);
  qsort(1,n);
  i:=1;
  f:=true;
  while i<=n do
    begin
      j:=i;
      while (a[j+1]=a[i])and(j<=n) do inc(j);
      if j-i+1>n div 2 then
        begin
          write(a[i],' ');
          f:=false;
        end;
      i:=j+1;
    end;
  if f then writeln(-1);
end.