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;
}

轉載于:https://www.cnblogs.com/irran/p/UVALive2678.html

總結

以上是生活随笔為你收集整理的UVALive2678:Subsequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。