题目大意：给定n个数的序列，让我们找前面k个区间的最大值之和，每个区间长度为n/k，如果有剩余的区间长度不足n/k则无视之。现在让我们找最小的k使得和严格大于m。
题解：二分k，然后求RMQ检验。
ST算法：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=200010;
int d[maxn][30];
int a[maxn];
void init_rmq(int n){
for(int i=0;i<n;i++)d[i][0]=a[i];
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]);
}
}
int query_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]);
}
bool check(int len,int m,int t){
int sum=0;
for(int i=1;i<=t;i++){
sum+=query_rmq((i-1)*len,i*len-1);
if(sum>m)return true;
}
return false;
}
int main(){
int n,m;
while(~scanf("%d %d
",&n,&m)){
if(n<0||m<0)break;
int sum=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
if(sum<=m){printf("-1
");continue;}
init_rmq(n);
int l=1,r=n,ans;
while(l<=r){
int mid=(l+r)>>1;
if(check(n/mid,m,mid)){
ans=mid;
r=mid-1;
}else l=mid+1;
}
printf("%d
",ans);
}
return 0;
}
暴力：
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=200010;
int a[maxn];
char c;
bool check(int len,int m,int t){
int x=-1,sum=0;
for(int i=0;i<t;i++){
for(int j=i*len+1;j<=(i+1)*len;j++)if(a[j]>x)x=a[j];
sum+=x;if(sum>m)return true;x=-1;
}
return false;
}
void scan(int &x){
while(c=getchar(),c<'0'||c>'9');x=c-'0';
while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';
}
int main(){
int n,m;
while(~scanf("%d%d
",&n,&m)){
if(n<0||m<0)break;
int sum=0;
for(int i=1;i<=n;i++){
scan(a[i]);
sum+=a[i];
}
if(sum<=m){printf("-1
");continue;}
int l=1,r=n,ans;
while(l<=r){
int mid=(l+r)>>1;
if(check(n/mid,m,mid)){
ans=mid;
r=mid-1;
}else l=mid+1;
}
printf("%d
",ans);
}
return 0;
}
令人惊讶的是暴力竟比ST快，因为复杂度少了一个log，所以做题时一定要多考虑，不要盲目码代码