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");
    }
}