找了半天都没找到太简单的==这个题面试n个人，可以分任意组数，每组选一个，得分总和严格大于k，问最少分几组

一说最大最小的不看分类也知道是rmq，其实自己是想到用二分的，可是你为什么不自己试着写写呢？？比赛的时候又不能确定思路再写，自己都WA多少遍还不知道思路对不对呢，这样不行啊。。。还有，标准二分的写法是不是得熟练一些啊。再有就是，这么大的数据量，多余的数组就彻底删了啊，MLE多少次不长记性==

/************
hdu3486
2016.1.19
748MS 18180K 1813 B C++
************/
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 200010
int  mx[MAXN][20], w[MAXN];
int n, k;
void rmqinit()
{
    for(int i = 1; i <= n; i++)  mx[i][0] = w[i];
    int m = (int)(log(n * 1.0) / log(2.0));
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
        {
            mx[j][i] = mx[j][i - 1];
            if(j + (1 << (i - 1)) <= n) mx[j][i] = max(mx[j][i], mx[j + (1 << (i - 1))][i - 1]);
        }
}
int rmqmax(int l,int r)
{
    int m = (int)(log((r - l + 1) * 1.0) / log(2.0));
    return max(mx[l][m] , mx[r - (1 << m) + 1][m]);
}
int fun(int x,int y)//len num
{
    int ans=0;
    for(int i=1;i<=y;i++)
    {
        ans+=rmqmax((i-1)*x+1,i*x);
        if(ans>k) return ans;
    }
    return ans;
}
int main()
{
   // freopen("cin.txt","r",stdin);
    while(~scanf("%d%d",&n,&k))
    {
        if(n==-1&&k==-1) break;
        int sum=0,l,r,mid,ans=0;
        bool flag=0;
        for(int i=1;i<=n;i++) {
            scanf("%d",&w[i]);
            sum+=w[i];
            if(w[i]>=k)
            {

                flag=1;
            }
        }
        if(flag) {printf("1\n");continue;}
        if(sum<=k)
        {
            printf("-1\n");
            continue;
        }
        rmqinit();
        l=1,r=n;
        while(l<=r)
        {
            mid=(l+r)/2;
          //  printf("l=%d,r=%d,mid=%d.",l,r,mid);
            int t=fun(n/mid,mid);//mid是每组个数
           // printf("t=%d\n",t);
            if(t>k)
            {
                r=mid-1;
                ans=mid;
            }
            else l=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

int mi[MAXN][17], mx[MAXN][17], w[MAXN];
int n, q;
void rmqinit()
{
    for(int i = 1; i <= n; i++) mi[i][0] = mx[i][0] = w[i];
    int m = (int)(log(n * 1.0) / log(2.0));
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
        {
            mx[j][i] = mx[j][i - 1];
            if(j + (1 << (i - 1)) <= n) mx[j][i] = max(mx[j][i], mx[j + (1 << (i - 1))][i - 1]);
            mi[j][i] = mi[j][i - 1];
            if(j + (1 << (i - 1)) <= n) mi[j][i] = min(mi[j][i], mi[j + (1 << (i - 1))][i - 1]);
        }
}
int rmqmin(int l,int r)
{
    int m = (int)(log((r - l + 1) * 1.0) / log(2.0));
    return min(mi[l][m] , mi[r - (1 << m) + 1][m]);
}
int rmqmax(int l,int r)
{
    int m = (int)(log((r - l + 1) * 1.0) / log(2.0));
    return max(mx[l][m] , mx[r - (1 << m) + 1][m]);
}

返回下标：

int mi[MAXN][17], mx[MAXN][17], w[MAXN];
int n, q;
void rmqinit()
{
    for(int i = 1; i <= n; i++) mi[i][0] = mx[i][0] = i;
    int m = (int)(log(n * 1.0) / log(2.0));
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
        {
            mx[j][i] = mx[j][i - 1];
            mi[j][i] = mi[j][i - 1];
            if(j + (1 << (i - 1)) <= n)
            {
                if(w[mx[j][i]] < w[mx[j + (1 << (i - 1))][i - 1]]) mx[j][i] = mx[j + (1 << (i - 1))][i - 1];
                if(w[mi[j][i]] > w[mi[j + (1 << (i - 1))][i - 1]]) mi[j][i] = mi[j + (1 << (i - 1))][i - 1];
            }
        }
}
int rmqmin(int l,int r)
{
    int m = (int)(log((r - l + 1) * 1.0) / log(2.0));
    if(w[mi[l][m]] > w[mi[r - (1 << m) + 1][m]]) return mi[r - (1 << m) + 1][m];
    else return mi[l][m];
}
int rmqmax(int l,int r)
{
    int m = (int)(log((r - l + 1) * 1.0) / log(2.0));
    if(w[mx[l][m]] < w[mx[r - (1 << m) + 1][m]]) return mx[r - (1 << m) + 1][m];
    else return mx[l][m];
}