PIPI OJ 1187: 子序列问题III(前缀和+二分查找)

本文主要是介绍PIPI OJ 1187: 子序列问题III(前缀和+二分查找)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1187: 子序列问题III

菜鸟生成记(78)

PIPIOJ上面有三道题意说明一模一样,但是数据范围不一样,三个不同的难度梯度

子序列问题I 1000 (1e3) O(n^3)的纯暴力即可解决

子序列问题II 10000 (1e4) O(n^2)前缀和预处理,优化区间求和

子序列问题III 100000 (1e5) O(n*log2n)前缀和预处理,优化区间求和,二分查找优化查找(lower_bound,或者手写不等值二分查找)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int a[110000];
/*
10 14
1 10  1  1  1  1  4  6  5  1
*/
int main()
{int n,s;while(cin>>n>>s){int len=200000;memset(a,0,sizeof(a));for(int i=1;i<=n;i++){cin>>a[i];a[i]+=a[i-1];//前缀和预处理 }/*前缀和a[x]:a[1]~a[x]的和a[y]:a[1]~a[y]的和a[y]-a[x]:a[x+1]~a[y]的和题目要找区间和大于等于s的最短区间转化为数学表达式就是a[y]-a[x]>=s;不等式移项a[y]>=a[x]+s;求出y-x最小值O(n)效率遍历前缀和数组O(log2n)查找最终时间复杂度O(n*log2n) */for(int i=1;i<=n;i++){//a[y]>=a[x]+s;int num=a[i]+s;int x=lower_bound(a+1,a+n+1,num)-a;if(x!=n+1)//查找失败的不计入长度计算 len=min(abs(x-i),len);}if(len==200000)cout<<0<<endl;elsecout<<len<<endl;}return 0;
}