先到的 k 趟里如果 A 线有 i 趟，B 线就有 k-i 趟。 用二分查找来找这个 i。 A 的 a[mid]（从 0 数起）要排进前 k 趟，比它先到的 B 线列车就不能超过 k-mid-1 趟，这等同于 b[k - mid - 1] + d >= a[mid]。 mid 变大时，这个条件只会从真变成假一次。 为真就 lo = mid + 1，为假就 hi = mid，这样缩小下去，大约 14 次就能确定 i。 第 k 趟列车是 A 的第 i 趟和 B 的第 k-i 趟中较晚到的那一趟。 中间位置在 Python 中是 (lo + hi) // 2，在 Java、C#、C、C++ 中是 (lo + hi) / 2，在 JavaScript、TypeScript 中是 Math.floor((lo + hi) / 2)，在 Craykon 中是 数学.商(lo + hi, 2)。 Python bisect 和 C++ std::lower_bound 是在一个列表里找一个值的工具，这个条件要同时看两个列表，不能直接拿来用，所以自己写了循环。 陷阱一：每个询问都把两张时刻表从头一趟一趟数到第 k 趟，在最大的输入上要数约 1.6 亿次。 d 每个询问都不同，所以合并一次的顺序也不能反复用。 这样写的 Python 解答没能在时限内跑完。 说实话，同样写法的 C 解答在这台电脑上 0.4 秒内就跑完了。 二分查找只有在慢的语言里才是非用不可的。 陷阱二：时刻相同时 A 在前。 所以条件和最后的比较都必须是 >=。 把两处写成 > 就会算成 B 在前，示例 1 的第二个询问 "2 5" 会得到 A 1 10 而不是 B 1 10，第三个询问会得到 B 2 20 而不是 A 2 20。 陷阱三：i 的范围不是 0 到 n，而是 max(0, k - m) 到 min(k, n)。 把范围取成 0 到 n，k - mid - 1 就会变成负数或者达到 m 以上。 Python 把负下标当作从末尾数起的位置，所以对示例 1 的第一个询问会悄悄输出 A 2 20（答案是 B 1 5），对第五个询问 "7 5" 则在读 b[5] 时因 IndexError 停下。 Java、C# 在两种情况下都会因异常停下，C、C++ 会发生什么是未定义的。 陷阱四：输出的时刻不是时刻表上的时刻，而是那一天实际到站的时刻。 B 线要加上 d。 不加的话，示例 1 的第二个询问会变成 B 1 5 而不是 B 1 10。 陷阱五：时刻和 d 都不超过 2 × 10^9，各自放得进 32 位的 int，但相加会大到 4 × 10^9 而溢出。 Java、C#、C、C++ 必须把时刻和 d 放在 long/long long 里。 在 Java 中放在 int 里，示例 2 的第二个询问中 4000000000 会变成 -294967296，输出 A 1 2000000000 而不是 B 2 4000000000。 Python 的整数没有大小限制，JavaScript、TypeScript、Craykon 的数在 2^53 以内是精确的，所以直接就对。
Pythonmain.py · 33 行
import sysdef main(): data = sys.stdin.buffer.read().split() n, m, q = int(data[0]), int(data[1]), int(data[2]) a = [int(x) for x in data[3:3 + n]] b = [int(x) for x in data[3 + n:3 + n + m]] out = [] pos = 3 + n + m for _ in range(q): k, d = int(data[pos]), int(data[pos + 1]) pos += 2 # 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. lo = max(0, k - m) hi = min(k, n) while lo < hi: mid = (lo + hi) // 2 # A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if b[k - mid - 1] + d >= a[mid]: lo = mid + 1 else: hi = mid i, j = lo, k - lo # k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if i == 0 or (j > 0 and b[j - 1] + d >= a[i - 1]): out.append("B %d %d" % (j, b[j - 1] + d)) else: out.append("A %d %d" % (i, a[i - 1])) print("\n".join(out))main()
JavaScriptmain.js · 27 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const m = data[1];const q = data[2];const a = data.slice(3, 3 + n);const b = data.slice(3 + n, 3 + n + m);const out = [];for (let x = 0; x < q; x++) { const k = data[3 + n + m + 2 * x]; const d = data[4 + n + m + 2 * x]; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. let lo = Math.max(0, k - m); let hi = Math.min(k, n); while (lo < hi) { const mid = Math.floor((lo + hi) / 2); // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } const i = lo; const j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i === 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) out.push("B " + j + " " + (b[j - 1] + d)); else out.push("A " + i + " " + a[i - 1]);}console.log(out.join("\n"));
TypeScriptmain.ts · 28 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const m = data[1];const q = data[2];const a: number[] = data.slice(3, 3 + n);const b: number[] = data.slice(3 + n, 3 + n + m);const out: string[] = [];for (let x = 0; x < q; x++) { const k = data[3 + n + m + 2 * x]; const d = data[4 + n + m + 2 * x]; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. let lo = Math.max(0, k - m); let hi = Math.min(k, n); while (lo < hi) { const mid = Math.floor((lo + hi) / 2); // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } const i = lo; const j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i === 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) out.push("B " + j + " " + (b[j - 1] + d)); else out.push("A " + i + " " + a[i - 1]);}console.log(out.join("\n"));
JavaMain.java · 42 行
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 m = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long[] a = new long[n]; long[] b = new long[m]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < m; i++) b[i] = Long.parseLong(st.nextToken()); StringBuilder out = new StringBuilder(); for (int x = 0; x < q; x++) { st = new StringTokenizer(in.readLine()); int k = Integer.parseInt(st.nextToken()); long d = Long.parseLong(st.nextToken()); // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. int lo = Math.max(0, k - m); int hi = Math.min(k, n); while (lo < hi) { int mid = (lo + hi) / 2; // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) { out.append("B ").append(j).append(' ').append(b[j - 1] + d).append('\n'); } else { out.append("A ").append(i).append(' ').append(a[i - 1]).append('\n'); } } System.out.print(out); }}
C#Main.cs · 38 行
using System;using System.Text;class Program{ static void Main() { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(p[0]), m = int.Parse(p[1]), q = int.Parse(p[2]); long[] a = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); long[] b = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); var sb = new StringBuilder(); for (int x = 0; x < q; x++) { p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int k = int.Parse(p[0]); long d = long.Parse(p[1]); // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. int lo = Math.Max(0, k - m); int hi = Math.Min(k, n); while (lo < hi) { int mid = (lo + hi) / 2; // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) sb.Append("B ").Append(j).Append(' ').Append(b[j - 1] + d).Append('\n'); else sb.Append("A ").Append(i).Append(' ').Append(a[i - 1]).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 34 行
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; vector<long long> a(n), b(m); for (auto& v : a) cin >> v; for (auto& v : b) cin >> v; while (q--) { int k; long long d; cin >> k >> d; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. int lo = max(0, k - m); int hi = min(k, n); while (lo < hi) { int mid = (lo + hi) / 2; // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) cout << "B " << j << ' ' << b[j - 1] + d << '\n'; else cout << "A " << i << ' ' << a[i - 1] << '\n'; } return 0;}
Cmain.c · 30 行
#include <stdio.h>static long long a[9000], b[9000];int main(void) { int n, m, q; if (scanf("%d %d %d", &n, &m, &q) != 3) return 0; for (int i = 0; i < n; i++) if (scanf("%lld", &a[i]) != 1) return 0; for (int i = 0; i < m; i++) if (scanf("%lld", &b[i]) != 1) return 0; for (int x = 0; x < q; x++) { int k; long long d; if (scanf("%d %lld", &k, &d) != 2) return 0; /* 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. */ int lo = k - m > 0 ? k - m : 0; int hi = k < n ? k : n; while (lo < hi) { int mid = (lo + hi) / 2; /* A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 */ if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; /* k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 */ if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) printf("B %d %lld\n", j, b[j - 1] + d); else printf("A %d %lld\n", i, a[i - 1]); } return 0;}
Craykonmain.cray · 40 行
첫줄 = 控制台.读数字();n = 첫줄[0];m = 첫줄[1];q = 첫줄[2];a = 控制台.读数字();b = 控制台.读数字();循环 (x = 0; x < q; x++){ 줄 = 控制台.读数字(); k = 줄[0]; d = 줄[1]; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. lo = 数学.较大值(0, k - m); hi = 数学.较小值(k, n); 当 (lo < hi) { mid = 数学.商(lo + hi, 2); // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 如果 (b[k - mid - 1] + d >= a[mid]) { lo = mid + 1; } 否则 { hi = mid; } } i = lo; j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 如果 (i == 0 || j > 0 && b[j - 1] + d >= a[i - 1]) { 控制台.输出("B " + j + " " + (b[j - 1] + d)); } 否则 { 控制台.输出("A " + i + " " + a[i - 1]); }}