Interviewe HDU

面试n个人，可以分任意组数，每组选一个，得分总和严格大于k，问最少分几组

就是暴力嘛。。。想到就去写吧。。

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _  ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = 200005, INF = 0x7fffffff;
int d[maxn][20], a[maxn];
int n, k;

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

}

int main()
{
    while(~scanf("%d%d", &n, &k) && n+k > 0)
    {
        int x = 1, y = 0, sum = 0;
        rep(i, 0, n)
        {
            scanf("%d", &a[i]);
            d[i][0] = a[i];
            y = max(y, a[i]);
            sum += a[i];
        }
        if(sum <= k)
        {
            printf("-1
");
            continue;
        }
        if(y > k)
        {
            printf("1
");
            continue;
        }
        for(int j=1; (1<<j) <= n; j++)
            for(int i=0; i+(1<<j)-1 < n; i++)
                d[i][j] = max(d[i][j-1], d[i+(1<<(j-1))][j-1]);
        x = max(2, k/y); y = n; //x为组数，y为总个数
        while(x <= y)
        {
            sum = 0;
            int m = y/x;   //m为区间长度
            for(int i=1; i<=x; i++)
                sum += rmq((i-1)*m, i*m-1);
            if(sum > k) break;
            x++;
        }
        printf("%d
", x);

    }


    return 0;
}