Hdu 3486 Interviewe（二分+RMQ）

思路：二分选择个数m即可，开始只考虑各个区间长度，未考虑是否能够选够m个，wa了几次。。。。

#include<cstdio>#include<cmath>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int maxn=2e5+50;int n,k;int a[maxn];int preLog2[maxn];int stTable[maxn][32];void st_prepare(int n,int *array){    preLog2[1]=0;    for(int i=2; i<=n; i++)    {        preLog2[i]=preLog2[i-1];        if((1<<preLog2[i]+1)==i) preLog2[i]++;    }    for(int i=n-1; i>=0; i--)    {        stTable[i][0]=array[i];        for(int j=1; (i+(1<<j)-1)<n; j++)        {            stTable[i][j]=max(stTable[i][j-1],stTable[i+(1<<j-1)][j-1]);        }    }}int query_max(int l,int r){    int len=r-l+1,k=preLog2[len];    return max(stTable[l][k],stTable[r-(1<<k)+1][k]);}int check(int m){    int sum=0,len=floor(n/m);    for(int i=0;i+len-1<len*m;i+=len)    {          sum+=query_max(i,i+len-1);          if(sum>k) return 1;    }    return 0;}int main(){    while(scanf("%d%d",&n,&k)!=EOF)    {        if(n<0||k<0) break;        for(int i=0; i<n; i++) scanf("%d",&a[i]);        st_prepare(n,a);        int l=1,r=n,ans=-1;        while(l<=r)        {            int mid=(l+r)/2;            if(check(mid))            {                ans=mid;                r=mid-1;            }            else l=mid+1;        }        if(ans==-1) printf("-1/n");        else printf("%d/n",ans);    }    return 0;}