题意：有n个人排队应聘然后每个人的能力值为v然后老板要把这些人分成m段，如果不能整除多出来就后面的人就不要了，然后从这m段里面选择每段的最大能力值加起来看是否能够大于老板需要的目标k
题解思路：因为要查询某个区间最大值不用更新用RMQ算法查比用线段树要快然后你一个一个分成m段是否可以是会超时的，但是如果v总值大于k那么如果分成a段不可以肯定存在分成b段可以（b>a）如果分成b段可以可能存在分成a段可以(a
#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cstdio> using namespace std; const int mx = 2e5+10; int dp[mx][20]; int n,m,sum; void st(){ sum = 0; for(int i =1; i <= n; i++){ scanf("%d",&dp[i][0]); sum+=dp[i][0]; } for(int j = 1; (1<<j) <= n; j++){ int d = (1<<j); for(int i= 1; i+d-1<=n; i++) dp[i][j] = max(dp[i][j-1],dp[i+d/2][j-1]); } } int rmq(int l,int r){ int k = log(r-l+1.0)/log(2.0); r = r-(1<<k)+1; return max(dp[l][k],dp[r][k]); } bool check(int len){ int d = n/len,ans = 0; len = d*len; for(int i = 1; i <= len; i+=d){ ans += rmq(i,i+d-1); } return ans > m; } int main(){ while(scanf("%d%d",&n,&m),n!=-1||m!=-1){ st(); if(sum <= m){ puts("-1"); continue; } int l = 1,r = n; while(l < r){ int mid = (l+r)>>1; if(check(mid)) r = mid; else l = mid+1; } printf("%d\n",r); } return 0; }