奶牛排队

梦里梦外; 2021-11-04 22:01 372阅读 0赞

# . 奶牛排队 #

*  [ 描述][Link 1]
 *  [ 提交][Link 2]
 *  [ 自定义测试][Link 3]

## 【题目描述】： ##

奶牛在熊大妈的带领下排成了一个序列。

显然，不同的奶牛身高不一定相同……

现在，奶牛们想知道，如果找出一些连续的奶牛区间，要求最左边的奶牛A是区间最矮的，最右边的B是区间最高的，且B高于A奶牛，且中间如果存在奶牛，则身高不能和A、B奶牛相同，问这样的一些奶牛区间最长的会有多少头奶牛。

从左到右给出奶牛的身高，请告诉它们符合条件的最多的奶牛数（答案可能是零、二，但不会是一）。

## 【输入描述】： ##

第一行一个数N（2<=N<=1000,000），表示奶牛的头数。

接下来N个数，每行一个数，从上到下表示从左到右奶牛的身高（1<=身高<=maxlongint）。

## 【输出描述】： ##

一行，表示最多奶牛数。

## 【样例输入】： ##

5 1 2 3 4 1

## 【样例输出】： ##

## 【样例说明】： ##

取第1头到第4头奶牛，满足条件且为最多。

## 【时间限制、数据范围及描述】： ##

时间：1s 空间：256M

30%的数据：2<=N<=10,000

50%的数据：2<=N<=100,000

100%的数据：2<=N<=1000,000

【解题思路】

本题有一点类似单调队列的思想，样例的话是取第1 头到第4 头奶牛，满足条件且为最多。

乍一看，像是最长上升子串，但是，这道题中间的数不要求必须是上升的，所以只要保证是第一个数比最后一个数小就行。

注意最后的特判（题目的要求）不可等于1！

【code】

1 #include <cstdio>
     2 #include <cstring>
     3 #include <algorithm>
     4 using namespace std;
     5 int f[1000005], h[1000005];
     6 int n,ans,i;
     7 int main(){
     8     scanf("%d",&n);
     9     for(i=1;i<=n;i++)
    10        scanf("%d",&h[i]);
    11     for(i=1;i<=n;i++){
    12         int id=i-1, j=i-1;
    13         while(j) {
    14             if(h[j]>=h[i]) break;
    15             if(h[f[j]+1]<h[id+1]) id=f[j];
    16             j=f[j];
    17         }
    18         f[i]=id;
    19         ans=max(ans, i-id);
    20     }
    21     if(ans==1)ans=0;
    22     printf("%d", ans);
    23     return 0;
    24 }

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int f[1000005], h[1000005];
    int n,ans,i;
    int main(){ 
    	scanf("%d",&n);
    	for(i=1;i<=n;i++)
    	   scanf("%d",&h[i]);
    	for(i=1;i<=n;i++){ 
    		int id=i-1, j=i-1;
    		while(j) { 
    			if(h[j]>=h[i]) break;
    			if(h[f[j]+1]<h[id+1]) id=f[j];
    			j=f[j];
    		}
    		f[i]=id;
    		ans=max(ans, i-id);
    	}
    	if(ans==1)ans=0;
    	printf("%d", ans);
    	return 0;
    }

转载于:https://www.cnblogs.com/66dzb/p/11192669.html

[Link 1]: http://220.180.209.150:38888/problem/391#tab-statement
[Link 2]: http://220.180.209.150:38888/problem/391#tab-submit-answer
[Link 3]: http://220.180.209.150:38888/problem/391#tab-custom-test