パン屋で一日に起きた出来事 q 個が、起きた順に与えられる。 出来事は二種類ある。 "bake t e c" は、時刻 t にパン c 個を一まとまりとして焼き、これらのパンは時刻 e まで（e を含む）売れることを表す。 "buy t k" は、時刻 t に客が一人、パンを k 個買いに来たことを表す。 客が来ると、パン屋はその時刻に売れるパン、つまり e ≥ t のパンだけを売る。 売れるパンのうち、期限 e が最も早いパンから順に k 個を渡す。 一まとまりのうち一部だけを売ることもあり、残りのパンは同じ期限のまま残る。 売れるパンが k 個より少なければ、あるパンをすべて渡す。 期限が同じパンどうしは、どれを先に渡しても答えは同じである。 同じ時刻の出来事は、入力に書かれた順に起きる。 buy の出来事ごとに一行に、客が受け取ったパンの数と、受け取ったパンごとの (e − t) の和（残り期限の合計）を空白で区切って出力せよ。 受け取ったパンがなければ "0 0" と出力する。
入力
一行目に q、続く q 行に出来事が一つずつ与えられる。 1 ≤ q ≤ 10,000、0 ≤ t ≤ e ≤ 1,000,000,000、1 ≤ c, k ≤ 1,000,000。 出来事の t は減らず、buy の出来事が一つ以上ある。
import heapqimport syslines = sys.stdin.read().split("\n")q = int(lines[0])heap = [] # [기한, 남은 개수]: 기한이 가장 이른 묶음이 heap[0]out = []for line in lines[1 : 1 + q]: w = line.split() t = int(w[1]) if w[0] == "bake": heapq.heappush(heap, [int(w[2]), int(w[3])]) continue need = int(w[2]) got = 0 total = 0 # 받은 빵마다 (기한 - t)를 더한 값 while need > 0 and heap: e, c = heap[0] if e < t: # 기한이 지난 묶음은 버린다(e == t이면 아직 팔 수 있다) heapq.heappop(heap) continue take = min(c, need) got += take total += take * (e - t) need -= take if take == c: heapq.heappop(heap) else: heap[0][1] = c - take # 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 out.append(f"{got} {total}")print("\n".join(out))
JavaScriptmain.js · 75 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);// 최소 힙: 칸마다 [기한, 남은 개수]. heap[0]이 기한이 가장 이른 묶음이고, i의 자식은 2i+1, 2i+2class MinHeap { constructor() { this.items = []; } get size() { return this.items.length; } top() { return this.items[0]; } push(x) { const a = this.items; a.push(x); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (a[parent][0] <= a[i][0]) break; [a[parent], a[i]] = [a[i], a[parent]]; i = parent; } } pop() { const a = this.items; const top = a[0]; const last = a.pop(); if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let small = i; if (l < a.length && a[l][0] < a[small][0]) small = l; if (r < a.length && a[r][0] < a[small][0]) small = r; if (small === i) break; [a[small], a[i]] = [a[i], a[small]]; i = small; } } return top; }}const heap = new MinHeap();const out = [];for (let i = 1; i <= q; i++) { const w = lines[i].trim().split(" "); const t = Number(w[1]); if (w[0] === "bake") { heap.push([Number(w[2]), Number(w[3])]); continue; } let need = Number(w[2]); let got = 0; let total = 0; // 받은 빵마다 (기한 - t)를 더한 값: 10^15까지라 배정밀도 수로도 정확하다 while (need > 0 && heap.size > 0) { const batch = heap.top(); const [e, c] = batch; if (e < t) { // 기한이 지난 묶음은 버린다(e === t이면 아직 팔 수 있다) heap.pop(); continue; } const take = Math.min(c, need); got += take; total += take * (e - t); need -= take; if (take === c) heap.pop(); else batch[1] = c - take; // 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 } out.push(`${got} ${total}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 81 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const q: number = Number(lines[0]);type Batch = [expiry: number, count: number];// 최소 힙: heap[0]이 기한이 가장 이른 묶음이고, i의 자식은 2i+1, 2i+2class MinHeap { private items: Batch[] = []; get size(): number { return this.items.length; } top(): Batch { return this.items[0]; } push(x: Batch): void { const a = this.items; a.push(x); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (a[parent][0] <= a[i][0]) break; [a[parent], a[i]] = [a[i], a[parent]]; i = parent; } } pop(): Batch { const a = this.items; const top = a[0]; const last = a.pop()!; // size > 0일 때만 부른다 if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let small = i; if (l < a.length && a[l][0] < a[small][0]) small = l; if (r < a.length && a[r][0] < a[small][0]) small = r; if (small === i) break; [a[small], a[i]] = [a[i], a[small]]; i = small; } } return top; }}const heap = new MinHeap();const out: string[] = [];for (let i = 1; i <= q; i++) { const w: string[] = lines[i].trim().split(" "); const t: number = Number(w[1]); if (w[0] === "bake") { heap.push([Number(w[2]), Number(w[3])]); continue; } let need: number = Number(w[2]); let got = 0; let total = 0; // 받은 빵마다 (기한 - t)를 더한 값: 10^15까지라 number로도 정확하다 while (need > 0 && heap.size > 0) { const batch: Batch = heap.top(); const [e, c] = batch; if (e < t) { // 기한이 지난 묶음은 버린다(e === t이면 아직 팔 수 있다) heap.pop(); continue; } const take: number = Math.min(c, need); got += take; total += take * (e - t); need -= take; if (take === c) heap.pop(); else batch[1] = c - take; // 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 } out.push(`${got} ${total}`);}console.log(out.join("\n"));
JavaMain.java · 44 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(in.readLine().trim()); // {기한, 남은 개수}를 기한이 이른 것부터 꺼내는 최소 힙 PriorityQueue<long[]> heap = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0])); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(in.readLine()); String kind = st.nextToken(); long t = Long.parseLong(st.nextToken()); if (kind.equals("bake")) { long e = Long.parseLong(st.nextToken()); long c = Long.parseLong(st.nextToken()); heap.add(new long[] {e, c}); continue; } long need = Long.parseLong(st.nextToken()); long got = 0; long total = 0; // 받은 빵마다 (기한 - t)를 더한 값: 10^15까지라 long이 필요하다 while (need > 0 && !heap.isEmpty()) { long[] batch = heap.peek(); if (batch[0] < t) { // 기한이 지난 묶음은 버린다(같은 시각이면 아직 팔 수 있다) heap.poll(); continue; } long take = Math.min(batch[1], need); got += take; total += take * (batch[0] - t); need -= take; if (take == batch[1]) heap.poll(); else batch[1] -= take; // 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 } out.append(got).append(' ').append(total).append('\n'); } System.out.print(out); }}
C#Main.cs · 44 行
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { int q = int.Parse(Console.ReadLine().Trim()); // PriorityQueue<값, 우선순위>: 우선순위(기한)가 이른 묶음부터 나온다. // 값은 남은 개수를 고칠 수 있게 길이 1짜리 배열로 둔다 var heap = new PriorityQueue<long[], long>(); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { string[] w = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long t = long.Parse(w[1]); if (w[0] == "bake") { heap.Enqueue(new long[] { long.Parse(w[3]) }, long.Parse(w[2])); continue; } long need = long.Parse(w[2]); long got = 0; long total = 0; // 받은 빵마다 (기한 - t)를 더한 값: 10^15까지라 long이 필요하다 while (need > 0 && heap.TryPeek(out long[] left, out long e)) { if (e < t) // 기한이 지난 묶음은 버린다(같은 시각이면 아직 팔 수 있다) { heap.Dequeue(); continue; } long take = Math.Min(left[0], need); got += take; total += take * (e - t); need -= take; if (take == left[0]) heap.Dequeue(); else left[0] -= take; // 개수만 줄인다: 우선순위(기한)는 그대로다 } sb.Append(got).Append(' ').Append(total).Append('\n'); } Console.Write(sb.ToString()); }}
C++main.cpp · 45 行
#include <algorithm>#include <iostream>#include <queue>#include <string>#include <utility>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int q; std::cin >> q; // (기한, 남은 개수): std::greater를 줘야 기한이 이른 것부터 나온다(기본은 최대 힙) using Batch = std::pair<long long, long long>; std::priority_queue<Batch, std::vector<Batch>, std::greater<Batch>> heap; std::string out; for (int i = 0; i < q; i++) { std::string kind; long long t; std::cin >> kind >> t; if (kind == "bake") { long long e, c; std::cin >> e >> c; heap.push({e, c}); continue; } long long need; std::cin >> need; long long got = 0, total = 0; // total: 받은 빵마다 (기한 - t)를 더한 값, 10^15까지 while (need > 0 && !heap.empty()) { auto [e, c] = heap.top(); heap.pop(); if (e < t) continue; // 기한이 지난 묶음은 버린다(같은 시각이면 아직 팔 수 있다) long long take = std::min(c, need); got += take; total += take * (e - t); need -= take; // top()은 고칠 수 없으니 꺼낸 뒤 남은 것을 다시 넣는다(기한이 같아 다시 맨 앞에 온다) if (take < c) heap.push({e, c - take}); } out += std::to_string(got) + " " + std::to_string(total) + "\n"; } std::cout << out; return 0;}
Cmain.c · 74 行
#include <stdio.h>#include <string.h>#define MAXQ 10000/* 최소 힙: 칸마다 (기한, 남은 개수). heap_e[0]이 기한이 가장 이르다 */static long long heap_e[MAXQ], heap_c[MAXQ];static int heap_size = 0;static void heap_swap(int i, int j) { long long t = heap_e[i]; heap_e[i] = heap_e[j]; heap_e[j] = t; t = heap_c[i]; heap_c[i] = heap_c[j]; heap_c[j] = t;}static void heap_push(long long e, long long c) { int i = heap_size++; heap_e[i] = e; heap_c[i] = c; while (i > 0 && heap_e[(i - 1) / 2] > heap_e[i]) { heap_swap((i - 1) / 2, i); i = (i - 1) / 2; }}static void heap_pop(void) { heap_size--; heap_e[0] = heap_e[heap_size]; heap_c[0] = heap_c[heap_size]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, small = i; if (l < heap_size && heap_e[l] < heap_e[small]) small = l; if (r < heap_size && heap_e[r] < heap_e[small]) small = r; if (small == i) break; heap_swap(small, i); i = small; }}int main(void) { int q; if (scanf("%d", &q) != 1) return 0; for (int i = 0; i < q; i++) { char kind[8]; long long t; scanf("%7s %lld", kind, &t); if (strcmp(kind, "bake") == 0) { long long e, c; scanf("%lld %lld", &e, &c); heap_push(e, c); continue; } long long need, got = 0, total = 0; /* total: 받은 빵마다 (기한 - t)를 더한 값, 10^15까지 */ scanf("%lld", &need); while (need > 0 && heap_size > 0) { if (heap_e[0] < t) { /* 기한이 지난 묶음은 버린다(같은 시각이면 아직 팔 수 있다) */ heap_pop(); continue; } long long take = heap_c[0] < need ? heap_c[0] : need; got += take; total += take * (heap_e[0] - t); need -= take; if (take == heap_c[0]) heap_pop(); else heap_c[0] -= take; /* 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 */ } printf("%lld %lld\n", got, total); } return 0;}
Craykonmain.cray · 91 行
// 최소 힙(목록 heap): 칸마다 [기한, 남은 개수]. heap[0]이 기한이 가장 이른 묶음이고, i의 자식은 2i+1, 2i+2힙넣기(heap, x){ heap.追加(x); i = heap.個数 - 1; 間 (i > 0) { 부모 = 数学.商(i - 1, 2); もし (heap[부모][0] <= heap[i][0]) { 抜ける; } t = heap[부모]; heap[부모] = heap[i]; heap[i] = t; i = 부모; }}힙빼기(heap){ heap[0] = heap[heap.個数 - 1]; heap.位置で取り除く(heap.個数 - 1); i = 0; 間 (真) { l = 2 * i + 1; r = l + 1; small = i; もし (l < heap.個数 && heap[l][0] < heap[small][0]) { small = l; } もし (r < heap.個数 && heap[r][0] < heap[small][0]) { small = r; } もし (small == i) { 抜ける; } t = heap[small]; heap[small] = heap[i]; heap[i] = t; i = small; }}q = コンソール.行読み().空白除去().数に();heap = [];繰り返す (n = 0; n < q; n++){ w = コンソール.行読み().空白除去().分ける(" "); t = w[1].数に(); もし (w[0] == "bake") { 힙넣기(heap, [w[2].数に(), w[3].数に()]); } でなければ { need = w[2].数に(); got = 0; total = 0; // 받은 빵마다 (기한 - t)를 더한 값 間 (need > 0 && heap.個数 > 0) { batch = heap[0]; e = batch[0]; c = batch[1]; もし (e < t) { 힙빼기(heap); } でなければ { take = 数学.小さい方(c, need); got += take; total += take * (e - t); need -= take; もし (take == c) { 힙빼기(heap); } でなければ { batch[1] = c - take; // 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 } } } コンソール.書く(got + " " + total); }}