当前位置: 代码迷 >> 综合 >> uva 2678 subsequnece(lower_bound)
  详细解决方案

uva 2678 subsequnece(lower_bound)

热度:18   发布时间:2024-01-09 02:43:47.0

https://vjudge.net/problem/UVALive-2678

第一感觉是用滑窗来做,确实可以借助滑窗做,还可以结合前缀和。

白书上借此介绍了lower_bound和upper_bound的用法。

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;int a[100050],b[100050];int main()
{int n,s;while(scanf("%d%d",&n,&s)!=EOF){for(int i=0;i<n;i++)scanf("%d",&a[i]);b[0]=a[0];for(int i=1;i<n;i++)b[i]=a[i]+b[i-1];int ans=n+1;for(int j=0;j<n;j++){if(b[j]<s) continue;int i=lower_bound(b,b+j,b[j]-s)-b;ans=min(ans,j-i+1);}printf("%d\n",ans==n+1?0:ans);}return 0;
}