A. Segment with Small Sum

題目內容

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

輸入 : 第一行有兩整數 nnss (1n105,1s1018)(1 \le n \le 10^5 , 1 \le s \le 10^{18}) 。第二行有 nn 個整數 aia_i ,代表陣列 aia_i 的元素。

輸出 : 輸出 11 個數字,代表最長符合區間段的長度,若無此區間段則輸出 00

解題想法

宣告一整數陣列 aa ,和一變數 ansans ,代表本題所求。

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

以下是迴圈步驟流程,其中將會判斷 tmptmp 是否超過 ss ,如果是就縮減區間左端,否則就增加區間右端,每次迴圈結束前都要執行 ans = max(R - L, ans) ,檢查本題所求。

alt-text alt-text alt-text alt-text alt-text alt-text alt-text alt-text

在本題的最後,輸出 $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;
}