中南oj 1364: Interview

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int n,a[200002],d[200002][30],k;
 
void init()   // 从点i开始   长1<<j     的最大值
{
    for(int i=1; i<=n; i++)
        d[i][0]=a[i];
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i+(1<<j)-1<=n; i++)
            d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
 
int rmq(int x,int y)
{
    int k=0;
    while(1<<(k+1)<=y-x+1)
        k++;
    return max(d[x][k],d[y-(1<<k)+1][k]);
}
 
int solve()
{
    int ans;
    int left=1,right=n;int m,l,r;
    int best=n+1;
    while(left<right)
    {
 
        int i;
        i=(left+right)/2;   // mid
 
 
        m=n/i;  //分为i段  每段m个人
        ans=0;
        for(int j=1; j<=i; j++)
        {
            l=(j-1)*m+1;
            r=j*m;
           // printf("l %d   r %d   zhi %d\n",l,r,rmq(l,r));
            ans+=rmq(l,r);
        }
        if(ans>k)
        {
            if(best>i)
                best=i;
            right=i-1;
        }
        else left=i+1;
    }
    if(best>n)
        return -1;
    return best;
 
}
 
int main()
{
    int i,j,m,t;
    while(scanf("%d%d",&n,&k))
    {
        if(n==-1&&k==-1)
            break;
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
 
        init();
        printf("%d\n",solve());
    }
 
 
    return 0;
}