51nod——1285 山峰和分段（暴力出奇迹）

深碍√TFBOYSˉ_ 2022-01-06 08:37 127阅读 0赞

要求每段的点数都一样，因此分的段数cnt肯定是n的因子，要求每段都有山峰，因此cnt肯定小于等于山峰数量。分段的宽度d=n/cnt，对山峰数量做一个前缀和，检查一下每一段的山峰数量是否没有增加即可。

1 ///暴力枚举段数
     2 #include <bits/stdc++.h>
     3 using namespace std;
     4 #define maxn 50050
     5 int high[maxn],num[maxn];
     6 
     7 int main(){
     8     std::ios::sync_with_stdio(0);
     9     cin.tie(0);
    10     int n; cin>>n;
    11     for(int i=1;i<=n;++i) cin>>high[i];
    12     for(int i=2;i<=n-1;++i){
    13         num[i]=num[i-1];
    14         if(high[i]>high[i-1]&&high[i]>high[i+1]) ++num[i];
    15     }
    16     int cnt=num[n]=num[n-1];
    17 
    18     int d;
    19     bool flag;
    20     int ans=0;
    21     while(cnt--){
    22         if(n%(cnt+1)) continue;
    23         d=n/(cnt+1);
    24         flag=1;
    25         for(int i=d;i<=n;i+=d){
    26             if(num[i]-num[i-d]==0){
    27                 flag=0;
    28                 break;
    29             }
    30         }
    31         if(flag){
    32             ans=cnt+1;
    33             break;
    34         }
    35     }
    36     cout<<ans<<endl;
    37 
    38     return 0;
    39 }

转载于:https://www.cnblogs.com/noobimp/p/10947057.html

发表评论取消回复

表情：

评论列表（有 0 条评论，127人围观）

还没有评论，来说两句吧...

相关阅读

相关 51nod 1043

题意：求在2\n位的数字中，前n位的和等于后n位的和的个数，比喻n=1的时候，11,22,33...99等数字都是的，还有1102，2121等都是满足要求的数字。n<=10

灰太狼/ 2022年08月21日 03:14/ 0 赞/ 216 阅读

相关 51nod1432 贪心

上船问题。排序之后枚举最大重量就可以了。 include <map> include <queue> include <sta

谁践踏了优雅/ 2022年07月29日 08:58/ 0 赞/ 192 阅读

相关 51Nod 1489 蜥蜴和地下室

[1489 蜥蜴和地下室][1489] ![ok.png][] 题目来源： [CodeForces][] 基准时间限制：1 秒空间限制：131072 KB 分值: 10

绝地灬酷狼/ 2022年07月08日 15:30/ 0 赞/ 152 阅读

相关 51nod-加农炮

一个长度为M的正整数数组A，表示从左向右的地形高度。测试一种加农炮，炮弹平行于地面从左向右飞行，高度为H，如果某处地形的高度大于等于炮弹飞行的高度H（A\[i\] >= H），

男娘i/ 2022年06月17日 14:08/ 0 赞/ 226 阅读

相关 51nod 1287 加农炮

[1287 加农炮][1287] ![ok.png][] 题目来源： [Codility][] 基准时间限制：1 秒空间限制：131072 KB 分值: 40 [难度：4

雨点打透心脏的1/2处/ 2022年06月09日 11:17/ 0 赞/ 212 阅读

相关 51nod-1770

为该问题添加一个话题隐藏话题 [1770 数数字][1770] 基准时间限制：1 秒空间限制：262144 KB 分值: 20 [难度：3级算法题][3] ![s

小灰灰/ 2022年05月28日 12:51/ 0 赞/ 197 阅读

相关 51nod-1433 0和5

小K手中有n张牌，每张牌上有一个一位数的数，这个字数不是0就是5。小K从这些牌在抽出任意张（不能抽0张），排成一行这样就组成了一个数。使得这个数尽可能大，而且可以被90整除。

一时失言乱红尘/ 2022年05月28日 12:13/ 0 赞/ 149 阅读

相关 51nod--1284

[1284 2 3 5 7的倍数][1284_2_3_5_7] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [难度：1级算法题][

分手后的思念是犯贱/ 2022年05月27日 11:22/ 0 赞/ 206 阅读

相关 51nod1584加权约数和

题目大意：求: \\\[ \\sum\_\{i-1\}^n\\sum\_\{j=1\}^nmax(i,j)\\sigma(i\j) \\\] 题解对于这个

- 日理万妓/ 2022年01月06日 16:07/ 0 赞/ 214 阅读

相关 51nod——1285 山峰和分段（暴力出奇迹）

　　要求每段的点数都一样，因此分的段数cnt肯定是n的因子，要求每段都有山峰，因此cnt肯定小于等于山峰数量。分段的宽度d=n/cnt，对山峰数量做一个前缀和，检查一下每一段的

深碍√TFBOYSˉ_/ 2022年01月06日 08:37/ 0 赞/ 128 阅读