UVALive2678:Subsequence

UVALive2678:Subsequence

---

题目大意

---

给定一个数组A和一个整数S。求数组A中，连续且之和不小于S的连续子序列长度最小值。

要求复杂度:Ο(n)

Solution

---

用变量L表示所选区间最左端下标，用变量R表示所选区间最右端下标，用变量sum表示所选区间的和。从左到右扫描一遍数组，如果sum比S小，则右移R，扩大所选区间，从而增大sum。通过不断的右移L达到遍历整个数组的目的。

Note

---

1. 当解不存在时需要输出0。不知道为什么题目中并没有明确的指出这一点，但如果不加以考虑一定会WA。
2. 数组中单个元素不超过int类型的表示范围，但子序列之和有可能超过，因此需要使用long long类型

AC-Code(C++)

---

Time:33ms

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <climits>
#include <ctime>using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 100000 + 10;/** 刘汝佳 训练指南 P48*/int A[maxn];int main(int argc, const char * argv[]) {//    freopen("input.txt", "r", stdin);int N,S;while(scanf("%d %d",&N,&S)==2){for(int i=0;i<N;i++){scanf("%d",A+i);}ll sum = 0; // long long is needed here!!!int R = 0;int L = 0;int ans = INF;while (L<N) {while(sum<S && R<N){sum += A[R++];}if(sum<S)break;ans = min(ans,R-L);sum -= A[L++];}// if solution doesn't exist, print 0 instead.ans = ans == INF ? 0 : ans;printf("%d\n",ans);}return 0;
}