NOIP 提高 2013 第一轮 第 33 题：完善程序（序列重排）第 1 空

题目

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

#include <stdio.h>
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 在当前子序列中出现的次数
 scanf("%d", &n);
 for (i = 1; i <= n; i++)
  scanf("%d", &a[i]);
 i = 1;
 j = 1;  //i, j 分别表示当前子序列的首尾，并保证其中至多有两个不同整数
 while ((j <= n) && (a[j] == a[i]))
  j++;
 cur1 = a[i];
 cur2 = a[j];  count1 =     (1)    ; //（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] ==     (2)    ) { //（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)           (3)    ; //（2 分）
     else           (4)    ; //（2 分）
     i++;
    }         (5)    ;   //（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++)
  printf("%d ", a[i]);
 return 0;
}

第 1 空应填（ ）

答案

j-1

题解

考点定位

窗口初始化时的同值段长度。

解题过程

进入①之前，i=1，j 从 1 开始向右跳过与 a[1] 相等的连续元素。此时 [1,j−1] 都是 cur1，a[j] 是遇到的第二种值。

因此 cur1 的个数是 (j−1)−1+1=j−1，cur2 的初始个数是 1。

答案：j-1。

易错提醒

在这个初始化位置 i 仍为 1，所以 j−i 与 j−1 相等，不存在解析所说的冲突。