hdu3486（RMQ）

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3486
二分+RMQ
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=200010;
 7 
 8 int a[maxn];
 9 int p[maxn][25];
10 int n,k;
11 void RMQ_INIT()
12 {
13     int k=log(n+0.0)/log(2.0);
14     for(int i=0;i<n;i++) p[i][0]=a[i];
15     for(int j=1;j<=k;j++)
16         for(int i=0;i+(1<<j)-1<n;i++)
17         p[i][j]=max(p[i][j-1],p[i+(1<<j-1)][j-1]);
18     return ;
19 }
20 int rmq(int x,int y)
21 {
22     int k=log(y*1.0-x+1)/log(2.0);
23     return max(p[x][k],p[y-(1<<k)+1][k]);
24 }
25 
26 int check(int r,int x)
27 {
28     int ans=0;
29     for(int i=0;i<x;i++)
30     {
31         ans+=rmq(i*r,i*r+r-1); //
32     }
33     return ans>k;
34 }
35 
36 int main()
37 {
38     while(scanf("%d%d",&n,&k))
39     {
40         int res;
41         int sum=0,flag=0;
42         if(n==-1&&k==-1) return 0;
43         for(int i=0;i<n;i++)
44         {
45             scanf("%d",&a[i]);
46             sum+=a[i];
47             if(a[i]>=k) flag=1;
48         }
49         if(flag) {
50             puts("1");
51             continue;
52         }
53         if(sum<=k) {
54             puts("-1");
55             continue;
56         }
57         RMQ_INIT();
58         int l=1,r=n;
59         while(l<=r)
60         {
61             int mid=(l+r)>>1;
62             if(check(n/mid,mid))
63                 {
64                     res=mid;
65                     r=mid-1;
66                 }
67             else l=mid+1;
68         }
69         printf("%d
",res);
70     }
71 }