农夫约翰的 N 头奶牛排成一排。
每头奶牛都用一个整数品种 ID 标识，队列中第 i 头奶牛的 ID 为 Bi。
约翰认为如果有一大段连续的奶牛都具有相同的品种 ID，他的奶牛就会更加的引人注目。
为了创造这样的连续段，约翰决定选取一个特定品种 ID，并从队列中剔除所有具有此 ID 的奶牛。
请帮助约翰确定，他通过这样做，能够获得的具有相同品种 ID 的最大奶牛连续段的长度。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个 Bi。
输出格式
输出具有相同品种 ID 的最大奶牛连续段的长度。
数据范围
1≤N≤1000,
0≤Bi≤106,
不含所有奶牛品种都相同的数据。
输入样例：
|
1 |
9 2 7 3 7 7 3 7 5 7 |
输出样例：
样例解释
最初队列中奶牛的品种 ID 依次为 2,7,3,7,7,3,7,5,7。
我们去掉所有品种 ID 为 3 的奶牛，剩下的奶牛的品种 ID 依次为 2,7,7,7,7,5,7。
最大的具有相同品种 ID 的奶牛连续段的长度为 4。
题目分析
N 给定的范围是 1000
那么时间复杂度可以是 O(n2) 级别的
那么就直接暴力就好了，枚举每个点（去掉），然后判断剩下的点中最长的长度是多少，取一个 max
时间复杂度O(n2)
|
1 |
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><iostream></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><algorithm></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><cstring></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><cmath></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><vector></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><stack></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><queue></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><sstream></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">x</span> <span class="token expression">first</span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">y</span> <span class="token expression">second</span></span> <span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span> <span class="token keyword">typedef</span> <span class="token keyword">long</span> <span class="token keyword">long</span> ll<span class="token punctuation">;</span> <span class="token keyword">typedef</span> pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> PII<span class="token punctuation">;</span> <span class="token keyword">const</span> <span class="token keyword">int</span> N <span class="token operator">=</span> <span class="token number">1010</span><span class="token punctuation">;</span> <span class="token keyword">const</span> <span class="token keyword">int</span> MOD <span class="token operator">=</span> <span class="token number">1000000007</span><span class="token punctuation">;</span> <span class="token keyword">const</span> <span class="token keyword">int</span> INF <span class="token operator">=</span> <span class="token number">0x3f3f3f3f</span><span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token function">gcd</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> <span class="token keyword">int</span> b<span class="token punctuation">)</span><span class="token punctuation">{<!-- --></span><span class="token keyword">return</span> b <span class="token operator">?</span> <span class="token function">gcd</span><span class="token punctuation">(</span>b<span class="token punctuation">,</span> a <span class="token operator">%</span> b<span class="token punctuation">)</span> <span class="token operator">:</span> a<span class="token punctuation">;</span><span class="token punctuation">}</span> <span class="token keyword">int</span> n<span class="token punctuation">;</span> <span class="token keyword">int</span> a<span class="token punctuation">[</span>N<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token function">check</span><span class="token punctuation">(</span><span class="token keyword">int</span> u<span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">int</span> res <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> flag <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> n<span class="token punctuation">;</span> i <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">if</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> u<span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> flag<span class="token punctuation">)</span> res <span class="token operator">++</span> <span class="token punctuation">;</span> <span class="token keyword">else</span> <span class="token punctuation">{<!-- --></span> flag <span class="token operator">=</span> a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> res <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> ans <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span> res<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> ans<span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> cin <span class="token operator">>></span> n<span class="token punctuation">;</span> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token operator">-</span>INF<span class="token punctuation">;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> n<span class="token punctuation">;</span> i <span class="token operator">++</span> <span class="token punctuation">)</span> cin <span class="token operator">>></span> a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> n<span class="token punctuation">;</span> i <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> ans <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span> <span class="token function">check</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> cout <span class="token operator"><<</span> ans <span class="token operator"><<</span> endl<span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> |
微信扫一扫打赏
支付宝扫一扫打赏
