HDU 3486 RMQ+二分

題意

給一組數，分成M組，每一組的人數為n/m，剩下的人丢棄。每組取最大的數，問要得到嚴格大于某個數的總和，最少需要分多少組

題解

這種題分組題，很容易便能想到是二分。隻是注意一些邊界情況就可以了，比如說選取的組位置邊界。

注意事項

處理問題不要刻意追求巧妙，選擇最穩妥的方式在大多數時候反而會更好。

代碼

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<string>
#define UP(i,l,h) for(int i=l;i<h;i++)
#define DOWN(i,h,l) for(int i=h-1;i>=l;i--)
#define W(a) while(a)
#define MEM(a,b) memset(a,b,sizeof(a))
#define LL long long
#define INF 0x3f3f3f3f
#define MAXN 800010
#define MOD 1000000007
#define EPS 1e-3
using namespace std;

int a[];
int d[][];
int n,m;
void rmq_init() {
    UP(i,,n) {
        d[i][]=a[i];
    }
    for(int j=; (<<j)<=n; j++) {
        for(int i=; i+(<<j)-<n; i++) {
            d[i][j]=max(d[i][j-],d[i+(<<(j-))][j-]);
        }
    }
}

int rmq(int l,int r) {
    int k=;
    W((<<(k+))<=r-l+) {
        k++;
    }
    return max(d[l][k],d[r-(<<k)+][k]);
}

int main() {
    W(~scanf("%d%d",&n,&m)) {
        if(n<&&m<)
            break;
        MEM(d,);
        MEM(a,);
        UP(i,,n) {
            scanf("%d",&a[i]);
        }
        rmq_init();
        int lt=,rt=n;
        int ans=-;
        W(lt<=rt) {
            int mid=(lt+rt)/;
//            cout<<lt<<" "<<rt<<endl;
            int pos=n/mid;
            LL sum=;
            for(int i=; i<pos*mid; i+=pos) {
                sum+=rmq(i,i+pos-);
            }
//            cout<<sum<<" "<<mid<<" "<<pos<<endl;
            if(sum>m) {
                ans=mid;
                rt=mid-;
            }else{
                lt=mid+;
            }
        }
        printf("%d\n",ans);
    }
}

/*
3 499
200 200 100
*/