GitBook

这里写图片描述

刚开始感觉排序一下从大到小取 结果忽略了“子序列”的意思也就是不能改变顺序 就如 1 5 10 1 1 5 1 5 这一组 应该输出3而不是2

所以这个二分搜索就很好用

二分搜索体现在对于在数列中搜索比某个值大于等于的值的坐标 也就是函数lower_bound()的原理 这次没调用 自己尝试写了 经过多次修改和理解 终于得到了满意的结果

#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

#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 (尺取法)