按发生顺序给出面包店一天里发生的 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); }}