题目大意：给定n个数的序列，让我们找前面k个区间的最大值之和，每个区间长度为n/k，如果有剩余的区间长度不足n/k则无视之。现在让我们找最小的k使得和严格大于m。
题解：二分k，然后求RMQ检验。
ST算法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50 |
#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",&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\n");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\n",ans); } return
0; } |
暴力：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 |
#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",&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\n");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\n",ans); } return
0; } |
令人惊讶的是暴力竟比ST快，因为复杂度少了一个log，所以做题时一定要多考虑，不要盲目码代码
HDU 3486 Interviewe,布布扣,bubuko.com
原文：http://www.cnblogs.com/forever97/p/3576982.html