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;
}
原文链接: https://www.cnblogs.com/tflsnoi/p/12292027.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/328461
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
