3464. 【NOIP2013模拟联考6】秀姿势(sugata) (Standard IO)

Description

“蓝猫淘气三千问，看蓝猫，我有姿势我自豪！”话说能考上HYSBZ的孩纸们肯定都是很有姿势的孩纸们，但是大家普遍偏科，都只有一门科目考得好。已知HYSBZ的入学考试科目数量小于等于10^9，而有n个学生参加了入学考试。现在HYSBZ要刷人了，招生办每一次刷人会把一个科目考得好的人全部刷掉，但是最多不能刷超过K次。（刷就是不录取）而HYSBZ的校长看录取名单时，最喜欢看的就是连续都是同一个科目考得好的人。他定义完美学生序列为连续且考得好的科目都为同一门的学生序列。现在招生办主任想让你帮他设计一种录取方案，使得最长的完美学生连续子序列尽量长。

 

Input

共N+1行，第一行2个正整数n，K，n表示入学考试人数，K表示刷人次数上限。
接下来N行，每行仅一个正整数Ai，为i号学生所考得好的科目。

 

Output

仅1个正整数，为最长的最长完美学生连续子序列。

 

Solutions

用队列维护一个区间，使得这个区间的擅长科目数量不超过 K+1， 那么统计出来的每个合法区间的众数的数量的最大值便为答案。具体操作 如下：

(1).首先添加第一个元素入队列，此时 Head=Tail=1

(2).接下来不断添加元素入队，当队列内元素种类不大于 K+1 时统计答案。

(3).当队列里的元素种类大于 K+1 时，不断将队列头部的元素出队，直到 队列内元素种类小于等于 K+1，这时要记得也要统计答案。 这便是这道题的算法。

时间复杂度 O(n)

 

代码

 

const
  maxn=1000000;
var
  n,k,ans:longint;
  f,a:array[0..100001]of longint;
  ha:array[0..1000000,1..2]of longint;
function max(o,p:longint):longint;
begin
  if o>p then exit(o);
  exit(p);
end;

function hash(x:longint):longint;
var
  i:longint;
begin
  i:=x mod maxn;
  while (ha[i,1]<>0) and (ha[i,1]<>x) do
    i:=(i+1) mod maxn;
  exit(i);
end;

procedure init;
var
  i:longint;
begin
  read(n,k);
  for i:=1 to n do
    read(a[i]);
end;

procedure main;
var
  i,j,head,tail,num:longint;
begin
  head:=1; tail:=0;
  ans:=1; num:=0;
  for i:=1 to n do
    begin
      inc(tail);
      j:=hash(a[i]);
      if ha[j,1]=0 then
        begin
          inc(num);
          ha[j,1]:=a[i];
          ha[j,2]:=1
        end else
        begin
          inc(ha[j,2]);
          ans:=max(ans,ha[j,2]);
          end;
      f[tail]:=a[i];
      while num>k+1 do
        begin
          j:=hash(f[head]);
          dec(ha[j,2]);
          if ha[j,2]=0 then
            begin
              ha[j,1]:=0;
              dec(num);
            end;
          inc(head);
        end;
    end;
end;

begin
  init;
  main;
  writeln(ans);
end.