#617. NOIP2013TG-28

NOIP2013TG-28

28.(完善程序)

(两元序列)试求一个整数序列中,最长的仅包含两个不同整数的连续子序列。如有多个子序列并列最长,输出任意一个即可。例如,序列 1 1 2 3 2 3 2 3 3 1 1 1 3 1 中,有两段满足条件的最长子序列,长度均为 77,分别用下划线和上划线标出。

#include<iostream>
using namespace std;

int main()
{
  const int SIZE=100;
  int n,i,j,a[SIZE],cur1,cur2,count1,count2,
      ans_length,ans_start,ans_end;
//cur1,cur2分别表示当前子序列中的两个不同整数
//count1,count2分别表示cur1,cur2在当前子序列中出现的次数
  cin>>n;
  for(i=1;i<=n;i++)
    cin>>a[i];
  i=1;
  j=1;
//i,j分别表示当前子序列的首尾,并保证其中至多有两个不同整数
  while((j<=n)&&(a[j]==a[i]))
    j++;
  cur1=a[i];
  cur2=a[j];
  count1=____________________//(3分)
  count2=1;
  ans_length=j-i+1;
  while(j<n){
    j++;
    if(a[j]==cur1)
      count1++;
    else if(a[j]==cur2)
      count2++;
    else{
        if(a[j-1]==____________________){ //(3分)
          while(count2>0){
            if(a[i]==cur1)
              count1--;
            else
              count2--;
            i++;
          }
          cur2=a[j];
          count2=1;
        }
        else{
          while(count1>0){
            if(a[i]==cur1)
              ____________________ //(2分)
            else
              ____________________ //(2分)
            i++;
          }
          ____________________ //(3分)
          count1=1;
        }
    }
    if(ans_length<j-i+1){
      ans_length=j-i+1;
      ans_start=i;
      ans_end=j;
    }
  }
  for(i=ans_start;i<=ans_end;i++)
    cout<<a[i]<<' ';
  return 0;
}

①:{{ input(1) }}

②:{{ input(2) }}

③:{{ input(3) }}

④:{{ input(4) }}

⑤:{{ input(5) }}