開啟章節選單
A. Segment with Small Sum
題目內容
給予一個有 個整數的陣列 ,假設此陣列的區間段 連續和小於等於 時為符合。你的任務就是找出最長符合區間段。
輸入 : 第一行有兩整數 和 。第二行有 個整數 ,代表陣列 的元素。
輸出 : 輸出 個數字,代表最長符合區間段的長度,若無此區間段則輸出 。
解題想法
宣告一整數陣列 ,和一變數 ,代表本題所求。
在輸入完 個整數 後,將會執行一 do ... while
迴圈,其中須宣告三個變數 ,代表區間左端 (目標刪除點)、區間右端 (目標增加點) 和目前區連續和。
以下是迴圈步驟流程,其中將會判斷 是否超過 ,如果是就縮減區間左端,否則就增加區間右端,每次迴圈結束前都要執行 ans = max(R - L, ans)
,檢查本題所求。
在本題的最後,輸出 $ans% 代表本題所求。
範例程式
#include <bits/stdc++.h> #define LL long long using namespace std; LL n, s, a[100005], ans = 0; int main() { cin >> n >> s; for (int i = 0; i < n; i++) cin >> a[i]; LL L = 0, R = 0, tmp = 0; do { if (tmp <= s && R < n) { tmp += a[R]; R++; } else { tmp -= a[L]; L++; } if (tmp <= s) ans = max(R - L, ans); } while (L < n || R < n); cout << ans << '\n'; return 0; }