首页 > 代码库 > 51Nod--1285-山峰和分段

51Nod--1285-山峰和分段

51Nod--1285-山峰和分段
 
1285 山峰和分段技术分享
题目来源: Codility
基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题
技术分享 收藏
技术分享 关注
用一个长度为N的整数数组A,描述山峰和山谷的高度。山峰需要满足如下条件, 0 < P < N - 1 且 A[P - 1] < A[P] > A[P + 1]。
 
技术分享
 
以上图为例,高度为:1 5 3 4 3 4 1 2 3 4 6 2。
现在要将整个山分为K段,要求每段的点数都一样,且每段中都至少存在一个山峰,问最多可以分为多少段。
Input
第1行:一个数N,表示数组的长度(1 <= N <= 50000)。
第2 - N + 1行:每行1个数Ai(1 <= Ai <= 10^9)。
Output
输出最多可以将山分为多少段。
Input示例
12
1
5
3
4
3
4
1
2
3
4
6
2
Output示例
3

 

 

题解: 数据量不大,使用直接法解决。就是题意有点难理解。

 

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
using namespace std; 
const int MAXN = 50005; 

int n, num[MAXN], cnt[MAXN];

bool Judge(int cur){
	for(int i=cur; i<=n; i+=cur){
		if(cnt[i] - cnt[i-cur] < 1){
			return false; 
		}
	}
	return true; 
} 

int main(){
	int ans, mot; 
	while(scanf("%d", &n) != EOF){
		for(int i=1; i<=n; ++i){
			scanf("%d", &num[i]); 
		}
		mot = 0; 
		cnt[1] = cnt[0] = 0; 
		for(int i=2; i<n; ++i){
			if(num[i] > num[i-1] && num[i] > num[i+1]){
				mot++; 
				cnt[i] = cnt[i-1] + 1; 
			}else{
				cnt[i] = cnt[i-1]; 
			}
		}
		cnt[n] = cnt[n-1]; 
		ans = 1; 
		if(mot == 0){
		    ans = 0; 
		}
		for(int i=mot; i>=2; --i){
			if( (n%i == 0) && Judge(n/i)){
				ans = i;  
				break; 
			}
		}
		printf("%d\n", ans );
	}
	return 0; 
}

  

 

51Nod--1285-山峰和分段