连续寿司

问题描述

东东和他的女朋友(幻想的)去寿司店吃晚餐(在梦中)，他发现了一个有趣的事情，这家餐厅提供的 n 个的寿司被连续的放置在桌子上 (有序)，东东可以选择一段连续的寿司来吃

东东想吃鳗鱼，但是东妹想吃金枪鱼。核 平 起 见，他们想选择一段连续的寿司（这段寿司必须满足金枪鱼的数量等于鳗鱼的数量，且前一半全是一种，后一半全是另外一种）我们用1代表鳗鱼，2代表金枪鱼。

比如，[2,2,2,1,1,1]这段序列是合法的，[1,2,1,2,1,2]是非法的。因为它不满足第二个要求。

东东希望你能帮助他找到最长的一段合法寿司，以便自己能吃饱。

Input

第一行：一个整数n（2 ≤ n ≤ 100000），寿司序列的长度。
第二行：n 个整数（每个整数不是 1 就是 2，意义如上所述）

Output

一个整数（代表东东可以选择的最长的一段连续的且合法的寿司）

Sample

Input: 
7
2 2 2 1 1 2 2
Output: 
4

Input: 
6
1 2 1 2 1 2
Output: 
2

Input: 
9
2 2 1 1 1 2 2 2 2
Output: 
6

Limitation

Time limit      1000 ms
Memory limit    262144 kb

解题思路

用一个双向队列来维护。

若队空或元素与队尾相同，或者元素与队首不同，则入队。

否则，遇到了元素与队尾不同的情况，即类似于AABBB此时加入A，则需要把队首的所有A弹出，保证序列只能为多个A-多个B或多个B-多个A。此时，需要计算原队列A-B长度，取min，再把这个min与答案取max。

源代码

#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

int solve(int n, int* arr) {
	int res = 0;
	deque<int> q;
	for (int i = 0; i < n; i++) {
		if (q.empty() || (!q.empty() && arr[i] == q.back())
			|| (!q.empty() && q.front() != arr[i])) {
			q.push_back(arr[i]);
		}

		else if (!q.empty() && q.back() != arr[i]) {
			int x = q.front();
			int c0 = 0;
			while (q.front() == x) {
				q.pop_front();
				c0++;
			}
			int c1 = q.size();
			res = max(res, 2 * min(c0, c1));
			q.push_back(arr[i]);
		}
	}
	if (!q.empty()) {
		int x = q.front();
		int c0 = 0;
		while (q.front() == x) {
			q.pop_front();
			c0++;
		}
		int c1 = q.size();
		res = max(res, 2 * min(c0, c1));
	}

	return res;
}

int main() {
	int n;
	while (!(cin >> n).eof()) {
		int* arr = new int[n + 10];
		for (int i = 0; i < n; i++)
			cin >> arr[i];
		int ans = solve(n, arr);
		cout << ans << endl;
	}

	return 0;
}