从二分查找到二分答案

题目链接：

2582 最短区间

现在给定一个整数s以及一个长度为n的整数数列a[0],a[1],a[2],a[3]....a[n-1]  (全为正数)，

请你求出总和不小于s的连续子序列的长度的最小值。如果解不存在，则输出0。

输入

第一行：两个整数，表示 s 与 n，其中1≤s≤10^9,1≤n≤500000；
第二行：n个用空格隔开的整数，表示 a[0] a[1] ... a[n-1]，其中对于任意a[i]有1≤a[i]≤10^9。

输出

输出总和不小于s的连续子序列的长度的最小值。
如果解不存在，则输出0。

输入样例

50 20
10 8 9 3 11 8 5 1 1 1 1 20 8 9 11 4 13 22 9 6

输出样例

4

方法一：前缀和，暴力算法O（N^2）（只能拿部分分）

#include<bits/stdc++.h>
using namespace std;
const int max_n=500000+10;
int n, s, a[max_n], sum[max_n];
int main()
{
	cin>>s>>n;
	for(int i=1; i<=n; i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	int ans=n+1;
	for(int i=1; i<=n; i++){
		if(sum[i]>=s){
			for(int j=i; j>=1; j--){
				if(sum[i]-sum[j-1]>=s)
					ans=min(ans,i-j+1);
			}
		}
	}
	if(ans==n+1)cout<<"0";
	else cout<<ans;
	
	return 0;
 } 

 方法二：前缀和改二分查找，其实是对方法一定的改进

#include<bits/stdc++.h>
using namespace std;
const int max_n=500000+10;
int n, s, a[max_n], sum[max_n];
int main()
{
	cin>>s>>n;
	for(int i=1; i<=n; i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	int ans=n+1;
	for(int i=1; i<=n; i++){
		if(sum[i]>=s){
			int j=upper_bound(sum,sum+i,sum[i]-s)-sum;
			ans=min(ans,i-j+1);
//			for(int j=i; j>=1; j--){
//				if(sum[i]-sum[j-1]>=s)
//					ans=min(ans,i-j+1);
//			}
		}
	}
	if(ans==n+1)cout<<"0";
	else cout<<ans;
	
	return 0;
 } 

方法二：二分答案区间长度，判断是否>=s(此代码有问题，需查找BUG更正)

#include<bits/stdc++.h>
using namespace std;
const int max_n=500000+10;
int n, s, a[max_n];
int sum[max_n];
bool check(int m)//检查m长度的区间和是否>=s 
{
	bool f=0;
	for(int i=1; i<=n-m+1; i++)
	{
		if(sum[i+m-1]-sum[i-1] >= s){
			f=1; 
			break;
		}
	}
	return f;
}
int main()
{
	cin>>s>>n;
	for(int i=1; i<=n; i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	int  l=1, r=n+1;
	while(l<r-1)//二分区间长度 
	{
		int mid=(l+r)>>1;
		if(check(mid))r=mid;
		else l=mid;
	} 
	cout<<r;
	return 0;
 }