首页 > 代码库 > 1281 山峰和旗子

1281 山峰和旗子

2024-10-13 00:04:39   217人阅读

用一个长度为N的整数数组A，描述山峰和山谷的高度。山峰需要满足如下条件， 0 < P < N - 1 且 A[P - 1] < A[P] > A[P + 1]。
 
技术分享
 
现在要在山峰上插上K个旗子，并且每个旗子之间的距离 >= K，问最多能插上多少个旗子（即求K的最大值）。两个山峰之间的距离为|P - Q|。
以上图为例，高度为：1 5 3 4 3 4 1 2 3 4 6 2。其中可以作为山峰的点为：1 3 5 10。
 
放2面旗子, 可以放在1 和 5。
放3面旗子, 可以放在1 5 和 10。
放4面旗子, 可以放在1 5 和 10，之后就放不下了。
所以最多可以放3面旗子。
Input
第1行：一个数N，表示数组的长度(1 <= N <= 50000)。
第2 - N + 1行：每行1个数Ai(1 <= Ai <= 10^9)。
Output
输出最多能插上多少面旗子（即求K的最大值）。
Input示例
12
1 
5 
3 
4 
3 
4 
1 
2 
3 
4 
6 
2
Output示例
3

思路：2分，找到可以插旗子的点，然后二分旗子个数，看是否满足有这么多个
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int a[50004];
 5 int b[50004];
 6 int s=0;
 7 
 8 int slove(int x){
 9     int sum=0,ssum=0;
10     for(int i=2;i<=s;i++){
11         sum+=b[i]-b[i-1];
12        // cout<<i<<" "<<sum<<endl;
13         if(sum>=x){
14             ssum++;sum=0;
15         }
16     }
17   //  cout<<endl;
18     return ssum+1;
19 }
20 int main(){
21     int n;
22     scanf("%d",&n);
23     for(int i=1;i<=n;i++){
24         scanf("%d",&a[i]);
25     }
26 
27     for(int i=2;i<n;i++){
28         if(a[i]>a[i-1]&&a[i]>a[i+1]){
29             b[++s]=i;
30         }
31     }
32     int l=1,r=s,mid;
33     int ans=0;
34     while(l<=r){
35         int mid=(l+r)>>1;
36         //cout<<mid<<" "<<slove(mid)<<endl;
37         if(slove(mid)>=mid){
38             ans=mid;
39             l=mid+1;
40         }
41         else r=mid-1;
42     }
43     cout<<ans<<endl;
44 }

 

1281 山峰和旗子


联系
我们