把结束的日子 r 固定下来，开始的日子越往前，日照之和与降雨之和都只增不减（因为值不小于 0）。 所以降雨条件只在开始的日子不早于某一天 lo 时成立，日照条件只在开始的日子不晚于某一天 hi 时成立。 以 r 结束的好时段就是开始的日子从 lo 到 hi 的 hi - lo + 1 个，其中最短的从 hi 开始。 r 增加一天时，lo 和 hi 都只会往后走。 所以三个指针（r、lo、hi）各自从头到尾只走一遍，一个询问的用时与 n 成正比。 和也不用重新加：带着 lo..r 的降雨之和与 hi..r 的日照之和，一天一天地加进、减出。 八种语言的解法样子几乎一样。 C、C++、Java、C#、JavaScript、TypeScript 可以像 rainSum -= rain[lo++] 这样在一行里边减边移动指针；Python 和 Craykon 不能在表达式里用 ++，所以分成两行写。 陷阱一：对每个开始的日子把结束的日子一天一天往后延、查看所有时段，一个询问要看约 4,000 万个时段，总共约 60 亿个。 有的输入一次雨也不下，中途也停不下来。 这样写的 Python 解答没能在时限内跑完，同样写法的 C 解答在这台电脑上对最大的输入也用了 12 秒。 陷阱二：lo 在 hi 之后时，没有以 r 结束的好时段。 不检查 lo <= hi 就加上 hi - lo + 1，会加上负数。 示例 1 的第一个询问会得到 2 而不是 4，第二个询问会得到 -1 1 3 而不是 0 0 0。 陷阱三：移动 hi 的循环里如果没有 hi < r，S 为 0 时 hi 会越过 r，把一天都没有的时段也数进去。 对示例 1 的第三个询问 "0 1"，JavaScript 输出 12 -1 3 而不是 5 1 1。 JavaScript 读到列表末尾之外只会给出 undefined，所以悄悄地出错；Python 会因 IndexError 停下，Java、C# 会因异常停下。 C、C++ 会发生什么是未定义的。 陷阱四：最短的时段有多个时，必须选开始最早的。 因为 r 是从前往后增加的，用 < 比较才会留下先找到的那个。 用 <= 比较，示例 1 的第三个询问中开始的日子会变成 6 而不是 1。 陷阱五：和会大到 9 × 10^12。 Java、C#、C、C++ 必须把和以及 S、R 放在 long/long long 里。 在 Java 中把和放在 int 里，示例 2 的第一个询问中 30 亿会变成 -1294967296，输出 0 0 0 而不是 1 3 1。 Python 的整数没有大小限制，JavaScript、TypeScript、Craykon 的数在 2^53 以内是精确的，所以直接就对。 好时段的个数最多约 4,050 万，放得进 int。
Pythonmain.py · 44 行
import sysdef solve(n, sun, rain, need, limit): """햇볕 합 ≥ need, 비 합 ≤ limit인 구간의 수와 가장 짧은 구간(길이, 시작 날).""" count = 0 best_len = best_start = 0 lo = 0 # 비 합이 limit 이하가 되는 가장 이른 시작 날 hi = 0 # 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) rain_sum = 0 # lo..r의 비 합 sun_sum = 0 # hi..r의 햇볕 합 for r in range(n): rain_sum += rain[r] while rain_sum > limit: rain_sum -= rain[lo] lo += 1 sun_sum += sun[r] while hi < r and sun_sum - sun[hi] >= need: sun_sum -= sun[hi] hi += 1 # 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if sun_sum >= need and lo <= hi: count += hi - lo + 1 if best_len == 0 or r - hi + 1 < best_len: best_len = r - hi + 1 best_start = hi + 1 return count, best_len, best_startdef main(): data = sys.stdin.buffer.read().split() n, q = int(data[0]), int(data[1]) sun = [int(x) for x in data[2:2 + n]] rain = [int(x) for x in data[2 + n:2 + 2 * n]] out = [] pos = 2 + 2 * n for _ in range(q): need, limit = int(data[pos]), int(data[pos + 1]) pos += 2 out.append("%d %d %d" % solve(n, sun, rain, need, limit)) print("\n".join(out))main()
JavaScriptmain.js · 37 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const q = data[1];const sun = data.slice(2, 2 + n);const rain = data.slice(2 + n, 2 + 2 * n);// 햇볕 합 ≥ need, 비 합 ≤ limit인 구간의 수와 가장 짧은 구간(길이, 시작 날)function solve(need, limit) { let count = 0; let bestLen = 0; let bestStart = 0; let lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 let hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) let rainSum = 0; // lo..r의 비 합 let sunSum = 0; // hi..r의 햇볕 합 for (let r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen === 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } return [count, bestLen, bestStart];}const out = [];for (let i = 0; i < q; i++) { out.push(solve(data[2 + 2 * n + 2 * i], data[3 + 2 * n + 2 * i]).join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 38 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const q = data[1];const sun: number[] = data.slice(2, 2 + n);const rain: number[] = data.slice(2 + n, 2 + 2 * n);// 햇볕 합 ≥ need, 비 합 ≤ limit인 구간의 수와 가장 짧은 구간(길이, 시작 날)function solve(need: number, limit: number): [number, number, number] { let count = 0; let bestLen = 0; let bestStart = 0; let lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 let hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) let rainSum = 0; // lo..r의 비 합 let sunSum = 0; // hi..r의 햇볕 합 for (let r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen === 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } return [count, bestLen, bestStart];}const out: string[] = [];for (let i = 0; i < q; i++) { out.push(solve(data[2 + 2 * n + 2 * i], data[3 + 2 * n + 2 * i]).join(" "));}console.log(out.join("\n"));
JavaMain.java · 45 行
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long[] sun = new long[n]; long[] rain = new long[n]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) sun[i] = Long.parseLong(st.nextToken()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) rain[i] = Long.parseLong(st.nextToken()); StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { st = new StringTokenizer(in.readLine()); long need = Long.parseLong(st.nextToken()); long limit = Long.parseLong(st.nextToken()); int count = 0, bestLen = 0, bestStart = 0; int lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 int hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) long rainSum = 0; // lo..r의 비 합 long sunSum = 0; // hi..r의 햇볕 합 for (int r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen == 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } out.append(count).append(' ').append(bestLen).append(' ').append(bestStart).append('\n'); } System.out.print(out); }}
C#Main.cs · 44 行
using System;using System.Text;class Program{ static void Main() { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(p[0]), q = int.Parse(p[1]); long[] sun = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); long[] rain = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); var sb = new StringBuilder(); for (int k = 0; k < q; k++) { p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long need = long.Parse(p[0]), limit = long.Parse(p[1]); int count = 0, bestLen = 0, bestStart = 0; int lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 int hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) long rainSum = 0; // lo..r의 비 합 long sunSum = 0; // hi..r의 햇볕 합 for (int r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen == 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } sb.Append(count).Append(' ').Append(bestLen).Append(' ').Append(bestStart).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 39 行
#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<long long> sun(n), rain(n); for (auto& v : sun) cin >> v; for (auto& v : rain) cin >> v; while (q--) { long long need, limit; cin >> need >> limit; int count = 0, bestLen = 0, bestStart = 0; int lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 int hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) long long rainSum = 0; // lo..r의 비 합 long long sunSum = 0; // hi..r의 햇볕 합 for (int r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen == 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } cout << count << ' ' << bestLen << ' ' << bestStart << '\n'; } return 0;}
Cmain.c · 36 行
#include <stdio.h>static long long sun[9000], rain[9000];int main(void) { int n, q; if (scanf("%d %d", &n, &q) != 2) return 0; for (int i = 0; i < n; i++) if (scanf("%lld", &sun[i]) != 1) return 0; for (int i = 0; i < n; i++) if (scanf("%lld", &rain[i]) != 1) return 0; for (int k = 0; k < q; k++) { long long need, limit; if (scanf("%lld %lld", &need, &limit) != 2) return 0; int count = 0, best_len = 0, best_start = 0; int lo = 0; /* 비 합이 limit 이하가 되는 가장 이른 시작 날 */ int hi = 0; /* 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) */ long long rain_sum = 0; /* lo..r의 비 합 */ long long sun_sum = 0; /* hi..r의 햇볕 합 */ for (int r = 0; r < n; r++) { rain_sum += rain[r]; while (rain_sum > limit) rain_sum -= rain[lo++]; sun_sum += sun[r]; while (hi < r && sun_sum - sun[hi] >= need) sun_sum -= sun[hi++]; /* 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 */ if (sun_sum >= need && lo <= hi) { count += hi - lo + 1; if (best_len == 0 || r - hi + 1 < best_len) { best_len = r - hi + 1; best_start = hi + 1; } } } printf("%d %d %d\n", count, best_len, best_start); } return 0;}
Craykonmain.cray · 45 行
첫줄 = 控制台.读数字();n = 첫줄[0];q = 첫줄[1];볕 = 控制台.读数字();비 = 控制台.读数字();循环 (k = 0; k < q; k++){ 줄 = 控制台.读数字(); need = 줄[0]; limit = 줄[1]; 센수 = 0; 짧은길이 = 0; 짧은시작 = 0; lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 hi = 0; // 볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) 비합 = 0; // lo..r의 비 합 볕합 = 0; // hi..r의 볕 합 循环 (r = 0; r < n; r++) { 비합 = 비합 + 비[r]; 当 (비합 > limit) { 비합 = 비합 - 비[lo]; lo = lo + 1; } 볕합 = 볕합 + 볕[r]; 当 (hi < r && 볕합 - 볕[hi] >= need) { 볕합 = 볕합 - 볕[hi]; hi = hi + 1; } // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 如果 (볕합 >= need && lo <= hi) { 센수 = 센수 + hi - lo + 1; 如果 (짧은길이 == 0 || r - hi + 1 < 짧은길이) { 짧은길이 = r - hi + 1; 짧은시작 = hi + 1; } } } 控制台.输出(센수 + " " + 짧은길이 + " " + 짧은시작);}