思路：二分选择个数m即可，开始只考虑各个区间长度，未考虑是否能够选够m个，wa了几次。。。。
#include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=2e5+50; int n,k; int a[maxn]; int preLog2[maxn]; int stTable[maxn][32]; void st_prepare(int n,int *array) { preLog2[1]=0; for(int i=2; i<=n; i++) { preLog2[i]=preLog2[i-1]; if((1<<preLog2[i]+1)==i) preLog2[i]++; } for(int i=n-1; i>=0; i--) { stTable[i][0]=array[i]; for(int j=1; (i+(1<<j)-1)<n; j++) { stTable[i][j]=max(stTable[i][j-1],stTable[i+(1<<j-1)][j-1]); } } } int query_max(int l,int r) { int len=r-l+1,k=preLog2[len]; return max(stTable[l][k],stTable[r-(1<<k)+1][k]); } int check(int m) { int sum=0,len=floor(n/m); for(int i=0;i+len-1<len*m;i+=len) { sum+=query_max(i,i+len-1); if(sum>k) return 1; } return 0; } int main() { while(scanf("%d%d",&n,&k)!=EOF) { if(n<0||k<0) break; for(int i=0; i<n; i++) scanf("%d",&a[i]); st_prepare(n,a); int l=1,r=n,ans=-1; while(l<=r) { int mid=(l+r)/2; if(check(mid)) { ans=mid; r=mid-1; } else l=mid+1; } if(ans==-1) printf("-1\n"); else printf("%d\n",ans); } return 0; }
