HDU-3486(Interviewe)

题意：给定一个长度为 n 的数组 s 和一个数 k，可以把 s 按顺序分成 m 组（m未知），但每一组的元素个数都必须相同，即每一组的元素个数为  n / m (末尾多余的元素舍去)，分别累加 m 个组的最大值的和 sum，要求 sum>k，求出最小的 m 使得这个条件满足。

分析：RMQ+暴力优化，首先对于分组数m，最大肯定是 n，那最小呢，我们先用RMQ求出整个数组的最大元素 tmp，那么 t=(k+1)/tmp 即是分组的最小数，为什么?因为 k+1 至少是由 t 个 tmp 组成的，而 tmp 又是整个数组的最大值，所以至少得分 t 组，

即 (t<=m<=n); 然后对于当前分组 m，求出每个组的长度cnt=n/m，跳着跳着用RMQ累加最大值就行了。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;

const int N = 200000+10;

int d[N][25],v[N];
int n,k;

void init()
{
    for(int i=1;i<=n;i++) d[i][0]=v[i];
    for(int i=1;(1<<i)<=n;i++)
    for(int j=1;j+(1<<i)-1<=n;j++)
        d[j][i]=max(d[j][i-1],d[j+(1<<(i-1))][i-1]);
}

int query(int l,int r)
{
    int k=0;
    while((1<<k)<=(r-l+1)) k++;
    k--;
    int ans=max(d[l][k],d[r-(1<<k)+1][k]);
    return ans;
}

int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        if(n<0&&k<0) break;

        for(int i=1;i<=n;i++) scanf("%d",&v[i]);
        init();
        int limit=query(1,n),m;
        for(m=max(1,(k+1)/limit);m<=n;m++)
        {
            int cnt=n/m;
            int ans=0;
            for(int j=1,p=0;p<m;p++,j+=cnt)
            {
                ans+=query(j,j+cnt-1);
                if(ans>k) break;
            }
            if(ans>k) break;
        }
        if(m<=n) printf("%d\n",m);
        else puts("-1");
    }
}