2012. 一排奶牛

农夫约翰的 N 头奶牛排成一排。

每头奶牛都用一个整数品种 ID 标识，队列中第 i 头奶牛的 ID 为 Bi。

约翰认为如果有一大段连续的奶牛都具有相同的品种 ID，他的奶牛就会更加的引人注目。

为了创造这样的连续段，约翰决定选取一个特定品种 ID，并从队列中剔除所有具有此 ID 的奶牛。

请帮助约翰确定，他通过这样做，能够获得的具有相同品种 ID 的最大奶牛连续段的长度。

输入格式

第一行包含整数 N。

接下来 N 行，每行包含一个 Bi。

输出格式

输出具有相同品种 ID 的最大奶牛连续段的长度。

数据范围

1≤N≤1000,
0≤Bi≤106,
不含所有奶牛品种都相同的数据。

输入样例：

9
2
7
3
7
7
3
7
5
7

输出样例：

4

样例解释
最初队列中奶牛的品种 ID 依次为 2,7,3,7,7,3,7,5,7。

我们去掉所有品种 ID 为 3 的奶牛，剩下的奶牛的品种 ID 依次为 2,7,7,7,7,5,7。

最大的具有相同品种 ID 的奶牛连续段的长度为 4。

代码：

/*
提炼一下题意，求的就是一段连续且只有2个元素区间内，单个元素的最大数量
所以可以直接使用双指针来解决
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, M = 1e6 + 10;
int a[N], cnt[M], ans;
int res;

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1, j = 1; i <= n; i++)
    {
        if (!cnt[a[i]])
            ans++;
        cnt[a[i]]++;

        while (ans > 2)
        {
            cnt[a[j]]--;
            if (cnt[a[j]] == 0)
                ans--;
            j++;
        }
        res = max(res, cnt[a[i]]);
    }

    cout << res << endl;

    return 0;
}

最后

以上就是热心铅笔为你收集整理的2012. 一排奶牛的全部内容，希望文章能够帮你解决2012. 一排奶牛所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。