기다릴수록 급해지는 진료 차례

import sysimport heapq data = sys.stdin.buffer.read().split()n, k = int(data[0]), int(data[1])arrive = [0] * nsev = [0] * ndur = [0] * nfor i in range(n):    arrive[i], sev[i], dur[i] = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i]) # 기다리는 사람의 급한 정도는 s + (T - a)인데, 모두 1분에 1씩 함께 오르니# 두 사람의 차례는 T와 상관없이 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람이 먼저waiting = []                  # (-(s - a), 번호)free = list(range(1, k + 1))  # 빈 진료실 번호(가장 작은 것이 맨 위)busy = []                     # (끝나는 시각, 진료실 번호)order = []seen = [0] * (k + 1)total_wait = 0nxt = 0  # 아직 오지 않은 첫 환자while len(order) < n:    # 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때    t = min(arrive[nxt] if nxt < n else float("inf"), busy[0][0] if busy else float("inf"))    while busy and busy[0][0] == t:          # ① 진료가 끝난 방부터 빈다        heapq.heappush(free, heapq.heappop(busy)[1])    while nxt < n and arrive[nxt] == t:      # ② 그 시각에 온 환자가 줄에 선다        heapq.heappush(waiting, (-(sev[nxt] - arrive[nxt]), nxt))        nxt += 1    while free and waiting:                  # ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다        room = heapq.heappop(free)        _, p = heapq.heappop(waiting)        order.append(p + 1)        seen[room] += 1        total_wait += t - arrive[p]        heapq.heappush(busy, (t + dur[p], room)) print(" ".join(map(str, order)))print(total_wait)print(" ".join(map(str, seen[1:])))

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // 작은 것이 맨 위에 오는 이진 힙. less(x, y)가 참이면 x가 y보다 먼저 나온다class Heap {  constructor(less) {    this.a = [];    this.less = less;  }  get size() {    return this.a.length;  }  top() {    return this.a[0];  }  push(x) {    const a = this.a;    a.push(x);    let i = a.length - 1;    while (i > 0) {      const p = (i - 1) >> 1;      if (!this.less(a[i], a[p])) break;      [a[i], a[p]] = [a[p], a[i]];      i = p;    }  }  pop() {    const a = this.a;    const top = a[0];    const last = a.pop();    if (a.length > 0) {      a[0] = last;      let i = 0;      for (;;) {        const l = 2 * i + 1;        const r = l + 1;        let m = i;        if (l < a.length && this.less(a[l], a[m])) m = l;        if (r < a.length && this.less(a[r], a[m])) m = r;        if (m === i) break;        [a[i], a[m]] = [a[m], a[i]];        i = m;      }    }    return top;  }} const [n, k] = data;const arrive = [];const sev = [];const dur = [];for (let i = 0; i < n; i++) {  arrive.push(data[2 + 3 * i]);  sev.push(data[3 + 3 * i]);  dur.push(data[4 + 3 * i]);} // 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람const key = (p) => sev[p] - arrive[p];const waiting = new Heap((x, y) => key(x) > key(y) || (key(x) === key(y) && x < y));const free = new Heap((x, y) => x < y); // 빈 진료실 번호const busy = new Heap((x, y) => x[0] < y[0] || (x[0] === y[0] && x[1] < y[1])); // [끝나는 시각, 진료실]for (let r = 1; r <= k; r++) free.push(r); const order = [];const seen = new Array(k + 1).fill(0);let totalWait = 0;let next = 0; // 아직 오지 않은 첫 환자while (order.length < n) {  // 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때  const t = Math.min(next < n ? arrive[next] : Infinity, busy.size > 0 ? busy.top()[0] : Infinity);  while (busy.size > 0 && busy.top()[0] === t) free.push(busy.pop()[1]); // ① 진료가 끝난 방부터 빈다  while (next < n && arrive[next] === t) waiting.push(next++); // ② 그 시각에 온 환자가 줄에 선다  while (free.size > 0 && waiting.size > 0) {    // ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다    const room = free.pop();    const p = waiting.pop();    order.push(p + 1);    seen[room]++;    totalWait += t - arrive[p];    busy.push([t + dur[p], room]);  }}console.log([order.join(" "), totalWait, seen.slice(1).join(" ")].join("\n"));

import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // 작은 것이 맨 위에 오는 이진 힙. less(x, y)가 참이면 x가 y보다 먼저 나온다class Heap<T> {  private readonly a: T[] = [];  constructor(private readonly less: (x: T, y: T) => boolean) {}  get size(): number {    return this.a.length;  }  top(): T {    return this.a[0];  }  push(x: T): void {    const a = this.a;    a.push(x);    let i = a.length - 1;    while (i > 0) {      const p = (i - 1) >> 1;      if (!this.less(a[i], a[p])) break;      [a[i], a[p]] = [a[p], a[i]];      i = p;    }  }  pop(): T {    const a = this.a;    const top = a[0];    const last = a.pop() as T;    if (a.length > 0) {      a[0] = last;      let i = 0;      for (;;) {        const l = 2 * i + 1;        const r = l + 1;        let m = i;        if (l < a.length && this.less(a[l], a[m])) m = l;        if (r < a.length && this.less(a[r], a[m])) m = r;        if (m === i) break;        [a[i], a[m]] = [a[m], a[i]];        i = m;      }    }    return top;  }} const [n, k] = data;const arrive: number[] = [];const sev: number[] = [];const dur: number[] = [];for (let i = 0; i < n; i++) {  arrive.push(data[2 + 3 * i]);  sev.push(data[3 + 3 * i]);  dur.push(data[4 + 3 * i]);} // 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람const key = (p: number): number => sev[p] - arrive[p];const waiting = new Heap<number>((x, y) => key(x) > key(y) || (key(x) === key(y) && x < y));const free = new Heap<number>((x, y) => x < y); // 빈 진료실 번호type Busy = [end: number, room: number];const busy = new Heap<Busy>((x, y) => x[0] < y[0] || (x[0] === y[0] && x[1] < y[1]));for (let r = 1; r <= k; r++) free.push(r); const order: number[] = [];const seen: number[] = new Array<number>(k + 1).fill(0);let totalWait = 0;let next = 0; // 아직 오지 않은 첫 환자while (order.length < n) {  // 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때  const t = Math.min(next < n ? arrive[next] : Infinity, busy.size > 0 ? busy.top()[0] : Infinity);  while (busy.size > 0 && busy.top()[0] === t) free.push(busy.pop()[1]); // ① 진료가 끝난 방부터 빈다  while (next < n && arrive[next] === t) waiting.push(next++); // ② 그 시각에 온 환자가 줄에 선다  while (free.size > 0 && waiting.size > 0) {    // ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다    const room = free.pop();    const p = waiting.pop();    order.push(p + 1);    seen[room]++;    totalWait += t - arrive[p];    busy.push([t + dur[p], room]);  }}console.log([order.join(" "), totalWait, seen.slice(1).join(" ")].join("\n"));

import java.io.*;import java.util.*; public class Main {    public static void main(String[] args) throws IOException {        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));        st.nextToken();        int n = (int) st.nval;        st.nextToken();        int k = (int) st.nval;        int[] arrive = new int[n], sev = new int[n], dur = new int[n];        for (int i = 0; i < n; i++) {            st.nextToken(); arrive[i] = (int) st.nval;            st.nextToken(); sev[i] = (int) st.nval;            st.nextToken(); dur[i] = (int) st.nval;        }         // 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람        PriorityQueue<Integer> waiting = new PriorityQueue<>(                Comparator.comparingInt((Integer p) -> -(sev[p] - arrive[p])).thenComparingInt(p -> p));        PriorityQueue<Integer> free = new PriorityQueue<>(); // 빈 진료실 번호        // {끝나는 시각, 진료실}: 시각이 이르고, 같으면 방 번호가 작은 것이 먼저        PriorityQueue<int[]> busy = new PriorityQueue<>((x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1]));        for (int r = 1; r <= k; r++) free.add(r);         StringBuilder order = new StringBuilder();        int[] seen = new int[k + 1];        long totalWait = 0; // 5×10^11까지 가서 int로는 넘친다        int called = 0, next = 0;        while (called < n) {            // 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때            int t = Integer.MAX_VALUE;            if (next < n) t = arrive[next];            if (!busy.isEmpty()) t = Math.min(t, busy.peek()[0]);            while (!busy.isEmpty() && busy.peek()[0] == t) free.add(busy.poll()[1]); // ① 진료가 끝난 방부터 빈다            while (next < n && arrive[next] == t) waiting.add(next++); // ② 그 시각에 온 환자가 줄에 선다            while (!free.isEmpty() && !waiting.isEmpty()) { // ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다                int room = free.poll();                int p = waiting.poll();                if (called++ > 0) order.append(' ');                order.append(p + 1);                seen[room]++;                totalWait += t - arrive[p];                busy.add(new int[] {t + dur[p], room});            }        }        StringBuilder sb = new StringBuilder();        sb.append(order).append('\n').append(totalWait).append('\n');        for (int r = 1; r <= k; r++) sb.append(seen[r]).append(r < k ? ' ' : '\n');        System.out.print(sb);    }}

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]), k = int.Parse(data[1]);        var arrive = new int[n];        var sev = new int[n];        var dur = new int[n];        for (int i = 0; i < n; i++)        {            arrive[i] = int.Parse(data[2 + 3 * i]);            sev[i] = int.Parse(data[3 + 3 * i]);            dur[i] = int.Parse(data[4 + 3 * i]);        }         // 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람        // PriorityQueue는 우선순위가 작은 것부터 꺼내니 (-(s - a), 번호)를 우선순위로 준다        var waiting = new PriorityQueue<int, (int, int)>();        var free = new PriorityQueue<int, int>();            // 빈 진료실 번호        var busy = new PriorityQueue<int, (int, int)>();     // 진료실, 우선순위 (끝나는 시각, 진료실)        for (int r = 1; r <= k; r++) free.Enqueue(r, r);         var order = new List<int>();        var seen = new int[k + 1];        long totalWait = 0; // 5×10^11까지 가서 int로는 넘친다        int next = 0;        while (order.Count < n)        {            // 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때            int t = int.MaxValue;            if (next < n) t = arrive[next];            if (busy.TryPeek(out _, out var b)) t = Math.Min(t, b.Item1);            while (busy.TryPeek(out int done, out var e) && e.Item1 == t) // ① 진료가 끝난 방부터 빈다            {                busy.Dequeue();                free.Enqueue(done, done);            }            while (next < n && arrive[next] == t) // ② 그 시각에 온 환자가 줄에 선다            {                waiting.Enqueue(next, (-(sev[next] - arrive[next]), next));                next++;            }            while (free.Count > 0 && waiting.Count > 0) // ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다            {                int room = free.Dequeue();                int p = waiting.Dequeue();                order.Add(p + 1);                seen[room]++;                totalWait += t - arrive[p];                busy.Enqueue(room, (t + dur[p], room));            }        }        var sb = new StringBuilder();        sb.Append(string.Join(' ', order)).Append('\n').Append(totalWait).Append('\n');        for (int r = 1; r <= k; r++) sb.Append(seen[r]).Append(r < k ? ' ' : '\n');        Console.Write(sb);    }}

#include <algorithm>#include <cstdint>#include <functional>#include <iostream>#include <queue>#include <utility>#include <vector> int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int n, k;    std::cin >> n >> k;    std::vector<int> arrive(n), sev(n), dur(n);    for (int i = 0; i < n; i++) std::cin >> arrive[i] >> sev[i] >> dur[i];     // priority_queue는 큰 것이 위다: std::greater를 주면 작은 것이 위    using P = std::pair<int, int>;    using MinHeap = std::priority_queue<P, std::vector<P>, std::greater<P>>;    // 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람    MinHeap waiting;  // (-(s - a), 번호)    MinHeap busy;     // (끝나는 시각, 진료실)    std::priority_queue<int, std::vector<int>, std::greater<int>> freeRooms;  // 빈 진료실 번호    for (int r = 1; r <= k; r++) freeRooms.push(r);     std::vector<int> order;    std::vector<int> seen(k + 1, 0);    long long totalWait = 0;  // 5×10^11까지 가서 int로는 넘친다    int next = 0;    while (static_cast<int>(order.size()) < n) {        // 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때        int t = next < n ? arrive[next] : INT32_MAX;        if (!busy.empty()) t = std::min(t, busy.top().first);        while (!busy.empty() && busy.top().first == t) {  // ① 진료가 끝난 방부터 빈다            freeRooms.push(busy.top().second);            busy.pop();        }        while (next < n && arrive[next] == t) {  // ② 그 시각에 온 환자가 줄에 선다            waiting.push({-(sev[next] - arrive[next]), next});            next++;        }        while (!freeRooms.empty() && !waiting.empty()) {  // ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다            int room = freeRooms.top();            freeRooms.pop();            int p = waiting.top().second;            waiting.pop();            order.push_back(p + 1);            seen[room]++;            totalWait += t - arrive[p];            busy.push({t + dur[p], room});        }    }    for (int i = 0; i < n; i++) std::cout << order[i] << (i + 1 < n ? ' ' : '\n');    std::cout << totalWait << '\n';    for (int r = 1; r <= k; r++) std::cout << seen[r] << (r < k ? ' ' : '\n');}

#include <stdio.h> #define MAXN 10000#define MAXK 100 /* 작은 것이 맨 위에 오는 이진 힙. 비교할 값을 long long 하나로 만들어 넣는다 */typedef struct {    long long a[MAXN + MAXK];    int size;} Heap; static void push(Heap *h, long long x) {    int i = h->size++;    h->a[i] = x;    while (i > 0) {        int p = (i - 1) / 2;        if (h->a[p] <= h->a[i]) break;        long long t = h->a[p];        h->a[p] = h->a[i];        h->a[i] = t;        i = p;    }} static long long pop(Heap *h) {    long long top = h->a[0];    h->a[0] = h->a[--h->size];    int i = 0;    for (;;) {        int l = 2 * i + 1, r = l + 1, m = i;        if (l < h->size && h->a[l] < h->a[m]) m = l;        if (r < h->size && h->a[r] < h->a[m]) m = r;        if (m == i) break;        long long t = h->a[m];        h->a[m] = h->a[i];        h->a[i] = t;        i = m;    }    return top;} static int arrive[MAXN], sev[MAXN], dur[MAXN], order[MAXN], seen[MAXK + 1];static Heap waiting, freeRooms, busy; int main(void) {    int n, k;    if (scanf("%d %d", &n, &k) != 2) return 0;    for (int i = 0; i < n; i++) scanf("%d %d %d", &arrive[i], &sev[i], &dur[i]);     /* 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람.       s - a는 -10^6 ~ 10^6이라 (10^6 - (s - a)) * 100000 + 번호가 작을수록 먼저다 */    /* 바쁜 방은 끝나는 시각 * 1000 + 방 번호(끝나는 시각은 1.01×10^8까지) */    for (int r = 1; r <= k; r++) push(&freeRooms, r);    long long totalWait = 0; /* 5×10^11까지 가서 int로는 넘친다 */    int called = 0, next = 0;    while (called < n) {        /* 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때 */        long long t = next < n ? arrive[next] : -1;        if (busy.size > 0 && (t < 0 || busy.a[0] / 1000 < t)) t = busy.a[0] / 1000;        while (busy.size > 0 && busy.a[0] / 1000 == t) push(&freeRooms, pop(&busy) % 1000); /* ① 진료가 끝난 방부터 빈다 */        while (next < n && arrive[next] == t) { /* ② 그 시각에 온 환자가 줄에 선다 */            push(&waiting, (1000000LL - (sev[next] - arrive[next])) * 100000 + next);            next++;        }        while (freeRooms.size > 0 && waiting.size > 0) { /* ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다 */            int room = (int)pop(&freeRooms);            int p = (int)(pop(&waiting) % 100000);            order[called++] = p + 1;            seen[room]++;            totalWait += t - arrive[p];            push(&busy, (t + dur[p]) * 1000 + room);        }    }    for (int i = 0; i < n; i++) printf("%d%c", order[i], i + 1 < n ? ' ' : '\n');    printf("%lld\n", totalWait);    for (int r = 1; r <= k; r++) printf("%d%c", seen[r], r < k ? ' ' : '\n');    return 0;}

// 작은 수가 맨 위에 오는 최소 힙(목록 heap). heap[0]이 가장 작고, i의 자식은 2i+1, 2i+2힙넣기(heap, x){    heap.넣기(x);    i = heap.개수 - 1;    동안 (i > 0)    {        부모 = 수학.몫(i - 1, 2);        만약 (heap[부모] <= heap[i])        {            그만;        }        t = heap[부모];        heap[부모] = heap[i];        heap[i] = t;        i = 부모;    }} 힙빼기(heap){    top = heap[0];    heap[0] = heap[heap.개수 - 1];    heap.자리빼기(heap.개수 - 1);    i = 0;    동안 (참)    {        l = 2 * i + 1;        r = l + 1;        small = i;        만약 (l < heap.개수 && heap[l] < heap[small])        {            small = l;        }        만약 (r < heap.개수 && heap[r] < heap[small])        {            small = r;        }        만약 (small == i)        {            그만;        }        t = heap[small];        heap[small] = heap[i];        heap[i] = t;        i = small;    }    돌려주기 top;} 첫줄 = 콘솔.수들읽기();n = 첫줄[0];k = 첫줄[1];arrive = [];sev = [];dur = [];반복 (i = 0; i < n; i++){    p = 콘솔.수들읽기();    arrive.넣기(p[0]);    sev.넣기(p[1]);    dur.넣기(p[2]);} // 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람// 힙에는 수 하나만 넣는다: (1000000 - (s - a)) * 100000 + 번호 — 작을수록 먼저(2×10^11까지라 정확하다)waiting = [];// 바쁜 방: 끝나는 시각 * 1000 + 방 번호(끝나는 시각은 1.01×10^8까지)busy = [];free = []; // 빈 진료실 번호반복 (r = 1; r <= k; r++){    힙넣기(free, r);} order = [];seen = 새목록(k + 1, 0);totalWait = 0;next = 0; // 아직 오지 않은 첫 환자동안 (order.개수 < n){    // 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때    t = -1;    만약 (next < n)    {        t = arrive[next];    }    만약 (busy.개수 > 0)    {        끝 = 수학.몫(busy[0], 1000);        만약 (t < 0 || 끝 < t)        {            t = 끝;        }    }    // ① 진료가 끝난 방부터 빈다    동안 (busy.개수 > 0 && 수학.몫(busy[0], 1000) == t)    {        힙넣기(free, 힙빼기(busy) % 1000);    }    // ② 그 시각에 온 환자가 줄에 선다    동안 (next < n && arrive[next] == t)    {        힙넣기(waiting, (1000000 - (sev[next] - arrive[next])) * 100000 + next);        next += 1;    }    // ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다    동안 (free.개수 > 0 && waiting.개수 > 0)    {        room = 힙빼기(free);        p = 힙빼기(waiting) % 100000;        order.넣기(p + 1);        seen[room] += 1;        totalWait += t - arrive[p];        힙넣기(busy, (t + dur[p]) * 1000 + room);    }}콘솔.쓰기(order.잇기(" "));콘솔.쓰기(totalWait);seen.자리빼기(0);콘솔.쓰기(seen.잇기(" "));