首页 > 代码库 > 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-山峰和分段
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。