题目描述
现在给定一个整数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
题解:
这是我做过的原题,但是一拿到手我还是直接用的暴力枚举,果然超时了,然后还是看别人的代码感觉像是尺取法,然后我翻我之前写的博客,发现就是一道原题(但是这里稍微写的不一样,这题我是从下标1开始的),说明我对尺取法掌握的还是不够好啊。
代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <deque>
#include <list>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <iterator>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double E = exp(1.0);
const int MOD = 1e9+7;
const int MAX = 5e5+5;
int s,n;
int a[MAX];
int sum[MAX];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while(cin >> s >> n)
{
for(int i = 1; i <= n; i++)
{
cin >> a[i];
sum[i] = a[i] + sum[i-1];
}
int min_len = inf;
/* 方法1: 前缀和+二分法
if(sum[n] < s)
{
cout << 0 << endl;// 如果所有的数的和都小于s,那不可能有>=s的
continue;
}
else
{
for(int st = 0; sum[st] <= sum[n] - s; st++)
{
int ed = lower_bound(sum+st,sum+n,sum[st]+s) - sum;
min_len = min(min_len,ed-st);
}
cout << min_len << endl;
}
*/
/* 方法2: 尺取法 */
int st = 1;
int ed = 1;
int sum = 0;
while(1)
{
while(ed <= n && sum < s)
{
sum += a[ed++];
}
if(sum < s)
{
break;
}
min_len = min(min_len,ed-st);
sum -= a[st++];
}
if(min_len > n)
{
min_len = 0;
}
cout << min_len << endl;
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)