import heapqimport sysdata = sys.stdin.read().split()n, q, limit = int(data[0]), int(data[1]), int(data[2])# 힙에 (달린 거리, 번호) 튜플을 넣는다: 튜플은 앞에서부터 견주니 거리가 같으면 번호가 작은 것이 위로 온다heap = [(int(data[3 + i]), i + 1) for i in range(n)]heapq.heapify(heap)out = []repaired = 0for j in range(q): d = int(data[3 + n + j]) if not heap: # 빌려줄 자전거가 없다 out.append("0") continue dist, bike = heapq.heappop(heap) out.append(str(bike)) dist += d if dist >= limit: # 딱 L이 되어도 정비소로 간다 repaired += 1 else: heapq.heappush(heap, (dist, bike))out.append(str(repaired))print("\n".join(out))
JavaScriptmain.js · 58 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q, limit] = data;// JavaScript에는 힙이 없어서 직접 만든다. dist[b] = b번 자전거가 달린 거리, heap에는 번호만 넣는다const dist = [0, ...data.slice(3, 3 + n)];// a번이 b번보다 먼저 나가야 하는가: 거리가 짧은 쪽, 같으면 번호가 작은 쪽const before = (a, b) => dist[a] < dist[b] || (dist[a] === dist[b] && a < b);const heap = [];function push(b) { heap.push(b); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (!before(heap[i], heap[parent])) break; [heap[i], heap[parent]] = [heap[parent], heap[i]]; i = parent; }}function pop() { const top = heap[0]; const last = heap.pop(); if (heap.length > 0) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1; const r = l + 1; let first = i; if (l < heap.length && before(heap[l], heap[first])) first = l; if (r < heap.length && before(heap[r], heap[first])) first = r; if (first === i) break; [heap[i], heap[first]] = [heap[first], heap[i]]; i = first; } } return top;}for (let b = 1; b <= n; b++) push(b);const out = [];let repaired = 0;for (let j = 0; j < q; j++) { const d = data[3 + n + j]; if (heap.length === 0) { out.push(0); // 빌려줄 자전거가 없다 continue; } const bike = pop(); out.push(bike); dist[bike] += d; // 10^12 남짓이라 number로도 정확하다 if (dist[bike] >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else push(bike);}out.push(repaired);console.log(out.join("\n"));
TypeScriptmain.ts · 60 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q, limit] = data;// TypeScript에도 힙이 없어서 직접 만든다. dist[b] = b번 자전거가 달린 거리, heap에는 번호만 넣는다const dist: number[] = [0, ...data.slice(3, 3 + n)];// a번이 b번보다 먼저 나가야 하는가: 거리가 짧은 쪽, 같으면 번호가 작은 쪽const before = (a: number, b: number): boolean => dist[a] < dist[b] || (dist[a] === dist[b] && a < b);const heap: number[] = [];function push(b: number): void { heap.push(b); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (!before(heap[i], heap[parent])) break; [heap[i], heap[parent]] = [heap[parent], heap[i]]; i = parent; }}function pop(): number { const top = heap[0]; const last = heap.pop() as number; if (heap.length > 0) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1; const r = l + 1; let first = i; if (l < heap.length && before(heap[l], heap[first])) first = l; if (r < heap.length && before(heap[r], heap[first])) first = r; if (first === i) break; [heap[i], heap[first]] = [heap[first], heap[i]]; i = first; } } return top;}for (let b = 1; b <= n; b++) push(b);const out: number[] = [];let repaired = 0;for (let j = 0; j < q; j++) { const d = data[3 + n + j]; if (heap.length === 0) { out.push(0); // 빌려줄 자전거가 없다 continue; } const bike = pop(); out.push(bike); dist[bike] += d; // 10^12 남짓이라 number로도 정확하다 if (dist[bike] >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else push(bike);}out.push(repaired);console.log(out.join("\n"));
JavaMain.java · 36 行
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()); int q = Integer.parseInt(st.nextToken()); long limit = Long.parseLong(st.nextToken()); // 10^12까지라 long // {달린 거리, 번호}를 넣는다. 거리가 짧은 것, 같으면 번호가 작은 것이 먼저 — 뺄셈이 아니라 Long.compare로 견준다 PriorityQueue<long[]> heap = new PriorityQueue<>( (a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1])); st = new StringTokenizer(br.readLine()); for (int b = 1; b <= n; b++) heap.add(new long[] {Long.parseLong(st.nextToken()), b}); StringBuilder sb = new StringBuilder(); int repaired = 0; st = new StringTokenizer(br.readLine()); for (int j = 0; j < q; j++) { long d = Long.parseLong(st.nextToken()); if (heap.isEmpty()) { // 빌려줄 자전거가 없다 sb.append("0\n"); continue; } long[] top = heap.poll(); sb.append(top[1]).append('\n'); top[0] += d; if (top[0] >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else heap.add(top); } sb.append(repaired).append('\n'); System.out.print(sb); }}
C#Main.cs · 37 行
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), q = int.Parse(data[1]); long limit = long.Parse(data[2]); // 10^12까지라 long // PriorityQueue<값, 우선순위>: 우선순위가 작은 것이 먼저 나온다 // 우선순위를 (달린 거리, 번호) 튜플로 주면 거리가 같을 때 번호가 작은 것이 먼저다 var heap = new PriorityQueue<int, (long, int)>(); for (int b = 1; b <= n; b++) heap.Enqueue(b, (long.Parse(data[2 + b]), b)); var sb = new StringBuilder(); int repaired = 0; for (int j = 0; j < q; j++) { long d = long.Parse(data[3 + n + j]); // TryDequeue는 비어 있으면 false를 돌려준다: 빌려줄 자전거가 없다 if (!heap.TryDequeue(out int bike, out (long dist, int id) key)) { sb.Append("0\n"); continue; } sb.Append(bike).Append('\n'); long dist = key.dist + d; if (dist >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else heap.Enqueue(bike, (dist, bike)); } sb.Append(repaired).Append('\n'); Console.Write(sb); }}
C++main.cpp · 42 行
#include <functional>#include <iostream>#include <queue>#include <utility>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; long long limit; // 10^12까지라 long long cin >> n >> q >> limit; // priority_queue는 기본이 큰 것 먼저다: greater를 주어 작은 것이 먼저 나오게 한다 // pair는 first부터 견주니 (달린 거리, 번호)로 넣으면 거리가 같을 때 번호가 작은 것이 먼저다 typedef pair<long long, int> Bike; priority_queue<Bike, vector<Bike>, greater<Bike>> heap; for (int b = 1; b <= n; b++) { long long w; cin >> w; heap.push({w, b}); } int repaired = 0; for (int j = 0; j < q; j++) { long long d; cin >> d; if (heap.empty()) { // 빌려줄 자전거가 없다 cout << "0\n"; continue; } Bike top = heap.top(); heap.pop(); cout << top.second << '\n'; top.first += d; if (top.first >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else heap.push(top); } cout << repaired << '\n'; return 0;}
Cmain.c · 69 行
#include <stdio.h>#include <stdlib.h>// C에는 힙이 없어서 직접 만든다. dist[b] = b번 자전거가 달린 거리, heap에는 번호만 넣는다static long long *dist;static int *heap;static int size = 0;// a번이 b번보다 먼저 나가야 하는가: 거리가 짧은 쪽, 같으면 번호가 작은 쪽static int before(int a, int b) { return dist[a] < dist[b] || (dist[a] == dist[b] && a < b);}static void push(int b) { int i = size++; heap[i] = b; while (i > 0) { int parent = (i - 1) / 2; if (!before(heap[i], heap[parent])) break; int t = heap[i]; heap[i] = heap[parent]; heap[parent] = t; i = parent; }}static int pop(void) { int top = heap[0]; heap[0] = heap[--size]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, first = i; if (l < size && before(heap[l], heap[first])) first = l; if (r < size && before(heap[r], heap[first])) first = r; if (first == i) break; int t = heap[i]; heap[i] = heap[first]; heap[first] = t; i = first; } return top;}int main(void) { int n, q; long long limit; // 10^12까지라 int에는 안 든다 if (scanf("%d %d %lld", &n, &q, &limit) != 3) return 0; dist = malloc((n + 1) * sizeof(long long)); heap = malloc((n + 1) * sizeof(int)); for (int b = 1; b <= n; b++) { scanf("%lld", &dist[b]); push(b); } int repaired = 0; for (int j = 0; j < q; j++) { long long d; scanf("%lld", &d); if (size == 0) { // 빌려줄 자전거가 없다 printf("0\n"); continue; } int bike = pop(); printf("%d\n", bike); dist[bike] += d; if (dist[bike] >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else push(bike); } printf("%d\n", repaired); free(dist); free(heap); return 0;}
Craykonmain.cray · 94 行
// 크레이콘에는 힙이 없어서 직접 만든다. dist[b] = b번 자전거가 달린 거리, heap에는 번호만 넣는다(번호는 0부터)첫줄 = コンソール.数読み();n = 첫줄[0];q = 첫줄[1];limit = 첫줄[2];dist = コンソール.数読み();타는거리 = コンソール.数読み();heap = [];// a번이 b번보다 먼저 나가야 하는가: 거리가 짧은 쪽, 같으면 번호가 작은 쪽먼저인가(a, b){ 返す dist[a] < dist[b] || dist[a] == dist[b] && a < b;}힙넣기(b){ heap.追加(b); i = heap.個数 - 1; 間 (i > 0) { 부모 = 数学.商(i - 1, 2); もし (!먼저인가(heap[i], heap[부모])) { 抜ける; } t = heap[i]; heap[i] = heap[부모]; heap[부모] = t; i = 부모; }}힙빼기(){ top = heap[0]; heap[0] = heap[heap.個数 - 1]; heap.位置で取り除く(heap.個数 - 1); i = 0; 間 (真) { l = 2 * i + 1; r = l + 1; first = i; もし (l < heap.個数 && 먼저인가(heap[l], heap[first])) { first = l; } もし (r < heap.個数 && 먼저인가(heap[r], heap[first])) { first = r; } もし (first == i) { 抜ける; } t = heap[i]; heap[i] = heap[first]; heap[first] = t; i = first; } 返す top;}繰り返す (b = 0; b < n; b++){ 힙넣기(b);}out = [];repaired = 0;それぞれ (d の中 타는거리){ もし (heap.個数 == 0) { out.追加(0); // 빌려줄 자전거가 없다 } でなければ { bike = 힙빼기(); out.追加(bike + 1); dist[bike] += d; もし (dist[bike] >= limit) { repaired += 1; } でなければ { 힙넣기(bike); } }}コンソール.書く(out.つなぐ("\n"));コンソール.書く(repaired);