A. Segment with Small Sum

題目內容

給予一個有 $n$ 個整數的陣列 $a_i$ ，假設此陣列的區間段 $[l, r]$ $(1 \le l \le r \le n)$ 連續和小於等於 $s$ 時為符合。你的任務就是找出最長符合區間段。

輸入 : 第一行有兩整數 $n$ 和 $s$ $(1 \le n \le 10^5 , 1 \le s \le 10^{18})$ 。第二行有 $n$ 個整數 $a_i$ ，代表陣列 $a_i$ 的元素。

輸出 : 輸出 $1$ 個數字，代表最長符合區間段的長度，若無此區間段則輸出 $0$。

解題想法

宣告一整數陣列 $a$ ，和一變數 $ans$ ，代表本題所求。

在輸入完 $n$ 個整數 $a_i$ 後，將會執行一 do ... while 迴圈，其中須宣告三個變數 $L, R, tmp$ ，代表區間左端 (目標刪除點)、區間右端 (目標增加點) 和目前區連續和。

以下是迴圈步驟流程，其中將會判斷 $tmp$ 是否超過 $s$ ，如果是就縮減區間左端，否則就增加區間右端，每次迴圈結束前都要執行 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;
}