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

题目

（两元序列）试求一个整数序列中，最长的仅包含两个不同整数的连续子序列。如有多 个子序列并列最长，输出任意一个即可。例如，序列 $\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;
}

第 3 空应填（ ）

答案

count1--

题解

考点定位

本题（两元序列第③空）考「左界收缩计数」,对应大纲 4.3.2 双指针（难度【3】）。

解题过程

③处左移 i 时对应计数减一：

``cpp if (a[i] == cur1) count1--; ``

答案：count1−−。

易错提醒

① 出队的元素属于哪个 cur 就减哪个计数；② while (count>0) 保证清到恰好剩 cur2 序列。