问题描述
问题分析
刚开始感觉排序一下从大到小取
结果忽略了“子序列”的意思也就是不能改变顺序
就如
1
5 10
1 1 5 1 5
这一组
应该输出3而不是2
所以这个二分搜索就很好用
二分搜索体现在对于在数列中搜索比某个值大于等于的值的坐标
也就是函数lower_bound()的原理
这次没调用
自己尝试写了
经过多次修改和理解
终于得到了满意的结果
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
| #include<stdio.h>
#include<algorithm>
using namespace std;
int sum[100200];
int n,m;
int find(int x) {
int lt=x,rt=n,mid;
while(rt-lt>0) {
mid=(lt+rt)/2;
if(sum[mid]-sum[x-1]<m) {
lt=mid+1;
} else {
rt=mid;
}
}
return lt;
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
scanf("%d %d",&n,&m);
sum[0]=0;
for(int i=1; i<=n; i++) {
int t;
scanf("%d",&t);
sum[i]=sum[i-1]+t;
}
if(sum[n]<m) {
printf("0\n");
continue;
}
int res=9999999;
for(int i=1; sum[i-1]+m<=sum[n]; i++) {
int t=find(i)-i+1;
res=min(res,t);
}
printf("%d\n",res);
}
return 0;
}
|
20160430补充:
一个月进步感人
二分结果
一次AC
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
| #include<stdio.h>
int a[100200];
int sum[100200];
int n,s;
bool judge(int m) {
for(int i=1; i<=n-m+1; i++) {
if(sum[i+m-1]-sum[i-1]>=s)
return true;
}
return false;
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
scanf("%d %d",&n,&s);
sum[0]=0;
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
if(!judge(n)) {
printf("0\n");
continue;
}
int l=1,r=n;
int res;
while(r>=l) {
int mid=(l+r)/2;
if(judge(mid)) {
res=mid;
r=mid-1;
} else
l=mid+1;
}
printf("%d\n",res);
}
return 0;
}
|
题目地址:【POJ】[3061]Subsequence
参考文章:[ACM] POJ 3061 Subsequence (尺取法）