AcWing|AcWing 每日一题 2022/5/6【2012. 一排奶牛】 c++|算法|图论|每日一题

AcWing 每日一题 2022/5/6【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。
题目分析

【AcWing|AcWing 每日一题 2022/5/6【2012. 一排奶牛】】N 给定的范围是 1000
那么时间复杂度可以是 O(n2) 级别的
那么就直接暴力就好了，枚举每个点（去掉），然后判断剩下的点中最长的长度是多少，取一个 max
时间复杂度O(n2)

#include #include #include #include #include #include #include #include#define x first #define y secondusing namespace std; typedef long long ll; typedef pair PII; const int N = 1010; const int MOD = 1000000007; const int INF = 0x3f3f3f3f; int gcd(int a, int b){return b ? gcd(b, a % b) : a; }int n; int a[N]; int check(int u) { int res = 0, ans = 0, flag = 0; for(int i = 0; i < n; i ++ ) { if(a[i] == u) continue; if(a[i] == flag) res ++ ; else { flag = a[i]; res = 1; } ans = max(ans, res); } return ans; }int main() { cin >> n; int ans = -INF; for(int i = 0; i < n; i ++ ) cin >> a[i]; for(int i = 0; i < n; i ++ ) { ans = max(ans, check(a[i])); } cout << ans << endl; return 0; }