沿着山脊有n段登山路连成一排，编号从1到n。
走第i段要花aᵢ的体力。
登山者选连续的第l段到第r段（1 ≤ l ≤ r ≤ n）作为一条“路线”。
路线中最费体力的一段坐缆车通过，不花体力。
即使最费体力的段有好几段，缆车也只坐一段。
如果其余各段所花体力之和不超过T，这条路线就是“走得动的路线”。
只有一段的路线花的体力是0，总是走得动。
第一行输出走得动的路线 (l, r) 的个数。
第二行输出走得动的路线中段数最多的那条的段数和起点编号l。
这样的路线有多条时，选l最小的。
6 5 3 9 2 4 1 7
14 3 1
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
把路线向右延长一段，“总和 − 最大值”不会变小（新的一段比最大值小就增加它自己，比最大值大就增加原来的最大值）。
所以可以用双指针：右端r一步步前进，左端l只在超出时前进，以r结尾的走得动的路线有r − l + 1条。
每次重新找窗口最大值是n²，所以用双端队列只保留“还可能成为最大值的位置”，从大到小排列：先弹出后面不大于新段的候选再放入，左端越过的候选从前面弹出。
例子：T = 5时，9 2 4坐缆车翻过9，花2 + 4 = 6，不行；2 4 1花2 + 1 = 3，可以。
陷阱一：只看总和、按总和 ≤ T移动窗口（忘了缆车）是错的。
陷阱二：超出时用if只缩一次，最长长度可能对，但个数会错 — 要用while。
陷阱三：左端越过的位置不从队列前面弹出，就会一直减去已经离开窗口的大段。
陷阱四：把比当前最大值小的段丢掉，最大值离开窗口后就不知道下一个最大值。
陷阱五：长度相同时用>=替换，会留下起点靠后的路线。
陷阱六：总和会到10^13，C、C++用long long，Java、C#用long（32位int只到约21亿）。
Python整数不会溢出，JavaScript、TypeScript、Craykon的数在2^53（约9×10^15）以内是精确的。
双端队列各语言不同：Python有collections.deque，Java有ArrayDeque，C++有std::deque；C#没有双端队列类，用数组加头尾下标来做（C也一样）。
JavaScript、TypeScript数组的shift()和Craykon列表的按位置移除(0)会把后面的元素全部前移，所以从前面弹出时只把头下标（head）加一。
import sysfrom collections import deque data = sys.stdin.buffer.read().split()n, limit = int(data[0]), int(data[1])a = [int(x) for x in data[2:2 + n]] dq = deque() # 창 안에서 '가장 힘든 구간' 후보의 자리. 힘이 큰 것부터 작은 것 순서로 남는다left = 0total = 0 # 창 안의 힘의 합count = 0best_len = 0best_start = 0for right in range(n): total += a[right] while dq and a[dq[-1]] <= a[right]: dq.pop() dq.append(right) # 가장 힘든 구간(dq[0])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while total - a[dq[0]] > limit: total -= a[left] if dq[0] == left: dq.popleft() left += 1 length = right - left + 1 count += length # right에서 끝나는 길은 시작이 left..right인 것 모두 if length > best_len: # 같으면 먼저 찾은(시작이 앞선) 것을 둔다 best_len = length best_start = left + 1print(count)print(best_len, best_start)const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const limit = data[1];const a = data.slice(2, 2 + n); // 덱: 배열 하나와 머리 번호. shift()는 뒤의 것을 모두 당기니 쓰지 않는다const dq = new Array(n);let head = 0;let tail = 0; // dq[head..tail-1]이 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터)let left = 0;let total = 0;let count = 0;let bestLen = 0;let bestStart = 0;for (let right = 0; right < n; right++) { total += a[right]; while (tail > head && a[dq[tail - 1]] <= a[right]) tail--; dq[tail++] = right; // 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq[head]] > limit) { total -= a[left]; if (dq[head] === left) head++; left++; } const length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; }}console.log(count + "\n" + bestLen + " " + bestStart);import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n: number = data[0];const limit: number = data[1];const a: number[] = data.slice(2, 2 + n); // 덱: 배열 하나와 머리 번호. shift()는 뒤의 것을 모두 당기니 쓰지 않는다const dq: number[] = new Array<number>(n).fill(0);let head = 0;let tail = 0; // dq[head..tail-1]이 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터)let left = 0;let total = 0;let count = 0;let bestLen = 0;let bestStart = 0;for (let right = 0; right < n; right++) { total += a[right]; while (tail > head && a[dq[tail - 1]] <= a[right]) tail--; dq[tail++] = right; // 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq[head]] > limit) { total -= a[left]; if (dq[head] === left) head++; left++; } const length: number = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; }}console.log(`${count}\n${bestLen} ${bestStart}`);import java.io.*;import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); long limit = Long.parseLong(st.nextToken()); long[] a = new long[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken()); // 창 안에서 '가장 힘든 구간' 후보의 자리. 힘이 큰 것부터 작은 것 순서로 남는다 ArrayDeque<Integer> dq = new ArrayDeque<>(); int left = 0, bestLen = 0, bestStart = 0; long total = 0; // 10^13까지 가서 int로는 넘친다 long count = 0; for (int right = 0; right < n; right++) { total += a[right]; while (!dq.isEmpty() && a[dq.peekLast()] <= a[right]) dq.pollLast(); dq.addLast(right); // 가장 힘든 구간(맨 앞)은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq.peekFirst()] > limit) { total -= a[left]; if (dq.peekFirst() == left) dq.pollFirst(); left++; } int length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; } } System.out.println(count); System.out.println(bestLen + " " + bestStart); }}using System; class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]); long limit = long.Parse(data[1]); var a = new long[n]; for (int i = 0; i < n; i++) a[i] = long.Parse(data[2 + i]); // .NET에는 Deque 클래스가 없다: 배열 하나와 머리·꼬리 번호로 덱을 만든다 var dq = new int[n]; int head = 0, tail = 0; // dq[head..tail-1]이 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터) int left = 0, bestLen = 0, bestStart = 0; long total = 0; // 10^13까지 가서 int로는 넘친다 long count = 0; for (int right = 0; right < n; right++) { total += a[right]; while (tail > head && a[dq[tail - 1]] <= a[right]) tail--; dq[tail++] = right; // 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq[head]] > limit) { total -= a[left]; if (dq[head] == left) head++; left++; } int length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; } } Console.WriteLine(count); Console.WriteLine($"{bestLen} {bestStart}"); }}#include <deque>#include <iostream>#include <vector>using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long limit; cin >> n >> limit; vector<long long> a(n); for (auto &x : a) cin >> x; deque<int> dq; // 창 안에서 '가장 힘든 구간' 후보의 자리. 힘이 큰 것부터 작은 것 순서로 남는다 int left = 0, bestLen = 0, bestStart = 0; long long total = 0; // 10^13까지 가서 int로는 넘친다 long long count = 0; for (int right = 0; right < n; right++) { total += a[right]; while (!dq.empty() && a[dq.back()] <= a[right]) dq.pop_back(); dq.push_back(right); // 가장 힘든 구간(dq.front())은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq.front()] > limit) { total -= a[left]; if (dq.front() == left) dq.pop_front(); left++; } int length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; } } cout << count << "\n" << bestLen << " " << bestStart << "\n"; return 0;}#include <stdio.h> #define MAXN 10000 static long long a[MAXN];static int dq[MAXN]; /* 덱: dq[head..tail-1]이 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터) */ int main(void) { int n; long long limit; if (scanf("%d %lld", &n, &limit) != 2) return 1; for (int i = 0; i < n; i++) scanf("%lld", &a[i]); int head = 0, tail = 0, left = 0, bestLen = 0, bestStart = 0; long long total = 0; /* 10^13까지 가서 int로는 넘친다 */ long long count = 0; for (int right = 0; right < n; right++) { total += a[right]; while (tail > head && a[dq[tail - 1]] <= a[right]) tail--; dq[tail++] = right; /* 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 */ while (total - a[dq[head]] > limit) { total -= a[left]; if (dq[head] == left) head++; left++; } int length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; } } printf("%lld\n%d %d\n", count, bestLen, bestStart); return 0;}첫줄 = 控制台.读数字();n = 첫줄[0];limit = 첫줄[1];a = 控制台.读数字(); // 덱: 목록 하나와 머리 번호. 자리빼기(0)은 뒤의 것을 모두 당기니 머리 번호만 옮긴다dq = [];head = 0; // dq[head..]가 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터)left = 0;total = 0;count = 0;bestLen = 0;bestStart = 0;循环 (right = 0; right < n; right++){ total += a[right]; 当 (dq.数量 > head && a[dq[dq.数量 - 1]] <= a[right]) { dq.按位置移除(dq.数量 - 1); } dq.添加(right); // 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 当 (total - a[dq[head]] > limit) { total -= a[left]; 如果 (dq[head] == left) { head += 1; } left += 1; } length = right - left + 1; count += length; 如果 (length > bestLen) { bestLen = length; bestStart = left + 1; }}控制台.输出(count);控制台.输出(bestLen + " " + bestStart);