题意： 给出 n 个序列，要求把它分成长度相等的m份，多余的去掉，要求每份的最大值之和大于 k。

         问最少要分成多少份。

分析： 二分区间，用rmq预处理出区间最大值。

#include 
     
      #include 
      
       #include 
       
        #define max(a,b)(a)>(b)?(a):(b)#define maxn 200005int val[maxn];int dp[maxn<<1][20];int k,n;void makermq(){    int i, j;    for(i = 1; i <= n; i++)        dp[i][0] = val[i];    for(j = 1; (1<
        
         <=n; j++)        for(i = 1;i+(1<
         
          <=n; i++)            dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);}int rmq(int l,int r){    int k = (int)(log((r-l+1)*1.0)/log(2.0));    return max(dp[l][k],dp[r-(1<
          
            k) return 1; } return sum>k;}inline bool scan_d(int &num) { char in; bool IsN=false; in=getchar(); if(in==EOF) return false; while(in!='-'&&(in<'0'||in>'9')) in=getchar(); if(in=='-'){ IsN=true;num=0;} else num=in-'0'; while(in=getchar(),in>='0'&&in<='9'){ num*=10,num+=in-'0'; } if(IsN) num=-num; return true;}int main(){ int i; int l, r, mid, res; while(scanf("%d %d",&n, &k)!=EOF) { if(n<0&&k<0) break; for(i = 1; i <= n; i++) scan_d(val[i]); makermq(); l = 1; r = n; res = -1; while(l<=r) { mid = (l+r)>>1; if(ok(mid)){ res = mid; r = mid-1; } else l = mid+1; } printf("%d\n",res); } return 0;}