一条单行道上有一个红绿灯。 时刻是 0, 1, 2, … 这样以秒为单位的整数。 信号从时刻 0 开始，依次重复绿灯 G 秒、红灯 R 秒。 也就是说，时刻 t 除以 G + R 的余数小于 G 时为绿灯，否则为红灯。 共有 n 辆车，第 i 辆车在时刻 aᵢ 到达红绿灯前，排到队尾。 到达时刻满足 a₁ ≤ a₂ ≤ … ≤ aₙ，同一时刻到达的车，编号小的排在前面。 每个绿灯时刻只有队首的一辆车通过，红灯时刻谁也不能通过。 如果队伍为空，车可以在到达的那一刻就通过。 第一行按编号顺序输出每辆车通过的时刻，用空格隔开。 第二行输出等得最久的车的编号和等待时间（通过时刻 − 到达时刻），用空格隔开。 如果等得最久的车有多辆，输出编号最小的那辆。 第一行给出 n、G、R，第二行给出用空格隔开的 a₁ … aₙ。
输入
1 ≤ n ≤ 5,000，1 ≤ G, R ≤ 10⁹，0 ≤ a₁ ≤ … ≤ aₙ ≤ 10⁹
输出
两行：第一行是 n 个通过时刻，第二行是车的编号和等待时间
样例 1 · stdin
6 3 2
0 0 1 4 4 9
stdout
0 1 2 5 6 10
5 2
样例 2 · stdin
1 1 1000000000
1
stdout
1000000001
1 1000000000
main.py
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
一秒一秒地走时钟来模拟，红灯长达 10 亿秒时要循环好几万亿次。 车只按排队顺序通过，所以直接求每辆车「最早能通过的时刻」：取到达时刻和前车通过时刻 + 1 中较晚的作为 t，若 m = t % (G + R) 不小于 G（红灯），就给 t 加上 (G + R) − m，跳到下一个周期的开头。 四个陷阱：① 余数恰好为 G 的时刻已经是红灯——写成 m > G 会把这一秒当成绿灯。 ② 不能和前车在同一秒通过，所以是 prev + 1（写成 prev 会一秒过两辆）。 ③ 周期 G + R 可达 2×10⁹，放不进 int（约 21 亿），通过时刻可达 5×10¹²——Java、C#、C、C++ 要用 long/long long 读入。 Python 不会溢出，JavaScript、TypeScript、Craykon 的数是 double，在 2^53 以内是精确的。 ④ 等待最久的车有多辆时取编号小的，所以用 > 比较（>= 会选到后面的车）。 取余 % 在八种语言里都是同一个符号，这里没有负数，所以不用担心各语言不同的负数取余规则。 Craykon 在一行里写两个值时，用 (best + 1) + " " + … 这样拼接字符串。
Pythonmain.py · 20 行
n, g, r = map(int, input().split())a = list(map(int, input().split()))period = g + rpassed = []prev = -1 # 앞 차가 지나간 시각(아직 없으면 -1)for arrive in a: t = max(arrive, prev + 1) # 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 m = t % period if m >= g: # 빨강이면 다음 초록(다음 주기의 처음)까지 기다린다 t += period - m passed.append(t) prev = tbest = 0 # 가장 오래 기다린 차의 자리(같으면 앞 번호)for i in range(n): if passed[i] - a[i] > passed[best] - a[best]: best = iprint(" ".join(map(str, passed)))print(best + 1, passed[best] - a[best])
JavaScriptmain.js · 19 行
const [n, g, r, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const period = g + r;const passed = [];let prev = -1; // 앞 차가 지나간 시각(아직 없으면 -1)for (const arrive of a) { let t = Math.max(arrive, prev + 1); // 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 const m = t % period; if (m >= g) t += period - m; // 빨강이면 다음 주기의 처음까지 기다린다 passed.push(t); prev = t;}let best = 0; // 가장 오래 기다린 차의 자리(같으면 앞 번호)for (let i = 0; i < n; i++) { if (passed[i] - a[i] > passed[best] - a[best]) best = i;}console.log(passed.join(" "));console.log(`${best + 1} ${passed[best] - a[best]}`);
TypeScriptmain.ts · 21 行
import { readFileSync } from "node:fs";const [n, g, r, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const period = g + r;const passed: number[] = [];let prev = -1; // 앞 차가 지나간 시각(아직 없으면 -1)for (const arrive of a) { let t = Math.max(arrive, prev + 1); // 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 const m = t % period; if (m >= g) t += period - m; // 빨강이면 다음 주기의 처음까지 기다린다 passed.push(t); prev = t;}let best = 0; // 가장 오래 기다린 차의 자리(같으면 앞 번호)for (let i = 0; i < n; i++) { if (passed[i] - a[i] > passed[best] - a[best]) best = i;}console.log(passed.join(" "));console.log(`${best + 1} ${passed[best] - a[best]}`);
JavaMain.java · 38 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;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()); long g = Long.parseLong(st.nextToken()); long r = Long.parseLong(st.nextToken()); long period = g + r; // 2×10⁹까지라 int를 넘는다 long[] a = new long[n]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken()); long[] passed = new long[n]; long prev = -1; // 앞 차가 지나간 시각(아직 없으면 -1) for (int i = 0; i < n; i++) { long t = Math.max(a[i], prev + 1); // 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 long m = t % period; if (m >= g) t += period - m; // 빨강이면 다음 주기의 처음까지 기다린다 passed[i] = t; prev = t; } int best = 0; // 가장 오래 기다린 차의 자리(같으면 앞 번호) StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) { if (passed[i] - a[i] > passed[best] - a[best]) best = i; if (i > 0) out.append(' '); out.append(passed[i]); } out.append('\n').append(best + 1).append(' ').append(passed[best] - a[best]); System.out.println(out); }}
C#Main.cs · 33 行
using System;using System.Linq;class Program{ static void Main() { long[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray(); int n = (int)first[0]; long g = first[1], r = first[2]; long period = g + r; // 2×10⁹까지라 int를 넘는다 long[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray(); long[] passed = new long[n]; long prev = -1; // 앞 차가 지나간 시각(아직 없으면 -1) for (int i = 0; i < n; i++) { long t = Math.Max(a[i], prev + 1); // 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 long m = t % period; if (m >= g) t += period - m; // 빨강이면 다음 주기의 처음까지 기다린다 passed[i] = t; prev = t; } int best = 0; // 가장 오래 기다린 차의 자리(같으면 앞 번호) for (int i = 0; i < n; i++) { if (passed[i] - a[i] > passed[best] - a[best]) best = i; } Console.WriteLine(string.Join(" ", passed)); Console.WriteLine($"{best + 1} {passed[best] - a[best]}"); }}
C++main.cpp · 28 行
#include <algorithm>#include <iostream>#include <vector>int main() { int n; long long g, r; std::cin >> n >> g >> r; const long long period = g + r; // 2×10⁹까지라 int를 넘는다 std::vector<long long> a(n), passed(n); for (long long& x : a) std::cin >> x; long long prev = -1; // 앞 차가 지나간 시각(아직 없으면 -1) for (int i = 0; i < n; i++) { long long t = std::max(a[i], prev + 1); // 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 long long m = t % period; if (m >= g) t += period - m; // 빨강이면 다음 주기의 처음까지 기다린다 passed[i] = t; prev = t; } int best = 0; // 가장 오래 기다린 차의 자리(같으면 앞 번호) for (int i = 0; i < n; i++) { if (passed[i] - a[i] > passed[best] - a[best]) best = i; std::cout << (i ? " " : "") << passed[i]; } std::cout << "\n" << best + 1 << " " << passed[best] - a[best] << "\n";}
Cmain.c · 28 行
#include <stdio.h>static long long a[5000], passed[5000];int main(void) { int n; long long g, r; scanf("%d %lld %lld", &n, &g, &r); long long period = g + r; /* 2×10⁹까지라 int를 넘는다 */ for (int i = 0; i < n; i++) scanf("%lld", &a[i]); long long prev = -1; /* 앞 차가 지나간 시각(아직 없으면 -1) */ for (int i = 0; i < n; i++) { long long t = a[i] > prev + 1 ? a[i] : prev + 1; /* 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 */ long long m = t % period; if (m >= g) t += period - m; /* 빨강이면 다음 주기의 처음까지 기다린다 */ passed[i] = t; prev = t; } int best = 0; /* 가장 오래 기다린 차의 자리(같으면 앞 번호) */ for (int i = 0; i < n; i++) { if (passed[i] - a[i] > passed[best] - a[best]) best = i; printf(i ? " %lld" : "%lld", passed[i]); } printf("\n%d %lld\n", best + 1, passed[best] - a[best]); return 0;}
Craykonmain.cray · 35 行
첫줄 = 控制台.读数字();n = 첫줄[0];g = 첫줄[1];r = 첫줄[2];a = 控制台.读数字();period = g + r;passed = [];// 앞 차가 지나간 시각(아직 없으면 -1)prev = -1;遍历 (arrive 在 a){ // 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 t = 数学.较大值(arrive, prev + 1); m = t % period; 如果 (m >= g) { // 빨강이면 다음 주기의 처음까지 기다린다 t += period - m; } passed.添加(t); prev = t;}// 가장 오래 기다린 차의 자리(같으면 앞 번호)best = 0;循环 (i = 0; i < n; i++){ 如果 (passed[i] - a[i] > passed[best] - a[best]) { best = i; }}控制台.输出(passed);控制台.输出(best + 1 + " " + (passed[best] - a[best]));