题解 P1407 【工资】

飞翔 · 2015-07-31 21:52:06 · 题解

不难，但蒟蒻的快排显然不行。因为空间限制是1MB……开数组？MLE准备~

好啦，闲话少说，下面进入正题！

首先，这题实际上就是求众数的改（wei）进（suo）版。于是，我们开了数组，结果MLE了……好吧，换方法。

我们可以开个变量a来记录一组数中谁出现的次数最多，具体实现请看代码。

program gold;
var
  i,j,t,n,a,s,x:longint;
begin
  readln(t);
  for i:=1 to t do
  begin
    a:=0;{初始化数据}
    read(n);
    for j:=1 to n do
    begin
      read(x);
      if a=0 then s:=x;
      **if s=x then inc(a) else dec(a);**{核心代码！如果s=x的话，a增加1，否则a减少1。也就是说，s等于上一个数，就增加a，反之s不等于上一个数，a就减1.如果a减成了零，说明此数不是众数，舍去}
    end;
    writeln(s);{输出}
  end;
end.