締め切りに間に合う 3D プリンターの注文を選ぶ

import heapqimport sys data = sys.stdin.read().split()n = int(data[0])jobs = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)]  # (걸리는 시간, 마감) jobs.sort(key=lambda job: job[1])  # 마감이 이른 것부터chosen = []  # 고른 주문의 시간들. heapq는 최소 힙이라 음수로 넣어 가장 긴 것을 꺼낸다total = 0  # 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각for t, d in jobs:    heapq.heappush(chosen, -t)    total += t    if total > d:        total += heapq.heappop(chosen)  # 마감을 넘으면 고른 것 가운데 가장 긴 주문을 뺀다 print(len(chosen), total)

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0]; // 최대 힙: heap[0]이 가장 크고, i의 자식은 2i+1, 2i+2class MaxHeap {  constructor() {    this.items = [];  }  get size() {    return this.items.length;  }  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] >= a[i]) 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 big = i;        if (l < a.length && a[l] > a[big]) big = l;        if (r < a.length && a[r] > a[big]) big = r;        if (big === i) break;        [a[big], a[i]] = [a[i], a[big]];        i = big;      }    }    return top;  }} const jobs = []; // [걸리는 시간, 마감]for (let i = 0; i < n; i++) jobs.push([data[1 + 2 * i], data[2 + 2 * i]]);jobs.sort((x, y) => x[1] - y[1]); // 마감이 이른 것부터 const chosen = new MaxHeap(); // 고른 주문의 시간들let total = 0; // 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각for (const [t, d] of jobs) {  chosen.push(t);  total += t;  if (total > d) total -= chosen.pop(); // 마감을 넘으면 고른 것 가운데 가장 긴 주문을 뺀다}console.log(`${chosen.size} ${total}`);

import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0]; // 최대 힙: heap[0]이 가장 크고, i의 자식은 2i+1, 2i+2class MaxHeap {  private items: number[] = [];   get size(): number {    return this.items.length;  }   push(x: number): void {    const a = this.items;    a.push(x);    let i = a.length - 1;    while (i > 0) {      const parent = (i - 1) >> 1;      if (a[parent] >= a[i]) break;      [a[parent], a[i]] = [a[i], a[parent]];      i = parent;    }  }   pop(): number {    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 big = i;        if (l < a.length && a[l] > a[big]) big = l;        if (r < a.length && a[r] > a[big]) big = r;        if (big === i) break;        [a[big], a[i]] = [a[i], a[big]];        i = big;      }    }    return top;  }} const jobs: [time: number, deadline: number][] = [];for (let i = 0; i < n; i++) jobs.push([data[1 + 2 * i], data[2 + 2 * i]]);jobs.sort((x, y) => x[1] - y[1]); // 마감이 이른 것부터 const chosen = new MaxHeap(); // 고른 주문의 시간들let total = 0; // 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각for (const [t, d] of jobs) {  chosen.push(t);  total += t;  if (total > d) total -= chosen.pop(); // 마감을 넘으면 고른 것 가운데 가장 긴 주문을 뺀다}console.log(`${chosen.size} ${total}`);

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Collections;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 n = Integer.parseInt(in.readLine().trim());        long[][] jobs = new long[n][]; // {걸리는 시간, 마감}. 마감은 int를 넘는다        for (int i = 0; i < n; i++) {            StringTokenizer st = new StringTokenizer(in.readLine());            jobs[i] = new long[] {Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken())};        }        Arrays.sort(jobs, (x, y) -> Long.compare(x[1], y[1])); // 마감이 이른 것부터         // PriorityQueue는 기본이 최소 힙이라 reverseOrder()로 가장 긴 것이 먼저 나오게 한다        PriorityQueue<Long> chosen = new PriorityQueue<>(Collections.reverseOrder());        long total = 0; // 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각        for (long[] job : jobs) {            chosen.add(job[0]);            total += job[0];            if (total > job[1]) total -= chosen.poll(); // 마감을 넘으면 가장 긴 주문을 뺀다        }        System.out.println(chosen.size() + " " + total);    }}

using System;using System.Collections.Generic; class Program{    static void Main()    {        int n = int.Parse(Console.ReadLine().Trim());        var jobs = new (long t, long d)[n]; // 마감은 int를 넘는다        for (int i = 0; i < n; i++)        {            string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            jobs[i] = (long.Parse(p[0]), long.Parse(p[1]));        }        Array.Sort(jobs, (x, y) => x.d.CompareTo(y.d)); // 마감이 이른 것부터         // PriorityQueue는 우선순위가 작은 것부터 나온다 → 우선순위를 -t로 주면 가장 긴 것이 먼저        var chosen = new PriorityQueue<long, long>();        long total = 0; // 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각        foreach (var (t, d) in jobs)        {            chosen.Enqueue(t, -t);            total += t;            if (total > d) total -= chosen.Dequeue(); // 마감을 넘으면 가장 긴 주문을 뺀다        }        Console.WriteLine($"{chosen.Count} {total}");    }}

#include <algorithm>#include <iostream>#include <queue>#include <utility>#include <vector> int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int n;    std::cin >> n;    std::vector<std::pair<long long, long long>> jobs(n); // (마감, 걸리는 시간). 마감은 int를 넘는다    for (auto& [d, t] : jobs) std::cin >> t >> d;    std::sort(jobs.begin(), jobs.end()); // 마감이 이른 것부터     std::priority_queue<long long> chosen; // 기본이 최대 힙: top()이 가장 긴 주문    long long total = 0; // 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각    for (auto [d, t] : jobs) {        chosen.push(t);        total += t;        if (total > d) { // 마감을 넘으면 가장 긴 주문을 뺀다            total -= chosen.top();            chosen.pop();        }    }    std::cout << chosen.size() << " " << total << "\n";}

#include <stdio.h>#include <stdlib.h> #define MAXN 10000 typedef struct {    long long t, d; /* 걸리는 시간, 마감(int를 넘는다) */} Job; static Job jobs[MAXN];static long long heap[MAXN]; /* 최대 힙: heap[0]이 가장 크다 */static int heap_size = 0; static int by_deadline(const void* x, const void* y) {    long long a = ((const Job*)x)->d, b = ((const Job*)y)->d;    return (a > b) - (a < b); /* 빼면 int를 넘을 수 있어 비교로 */} static void swap(long long* x, long long* y) {    long long t = *x;    *x = *y;    *y = t;} static void heap_push(long long x) {    int i = heap_size++;    heap[i] = x;    while (i > 0 && heap[(i - 1) / 2] < heap[i]) {        swap(&heap[(i - 1) / 2], &heap[i]);        i = (i - 1) / 2;    }} static long long heap_pop(void) {    long long top = heap[0];    heap[0] = heap[--heap_size];    int i = 0;    for (;;) {        int l = 2 * i + 1, r = l + 1, big = i;        if (l < heap_size && heap[l] > heap[big]) big = l;        if (r < heap_size && heap[r] > heap[big]) big = r;        if (big == i) break;        swap(&heap[big], &heap[i]);        i = big;    }    return top;} int main(void) {    int n;    scanf("%d", &n);    for (int i = 0; i < n; i++) scanf("%lld %lld", &jobs[i].t, &jobs[i].d);    qsort(jobs, n, sizeof(Job), by_deadline); /* 마감이 이른 것부터 */     long long total = 0; /* 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각 */    for (int i = 0; i < n; i++) {        heap_push(jobs[i].t);        total += jobs[i].t;        if (total > jobs[i].d) total -= heap_pop(); /* 마감을 넘으면 가장 긴 주문을 뺀다 */    }    printf("%d %lld\n", heap_size, total);    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;        big = i;        もし (l < heap.個数 && heap[l] > heap[big])        {            big = l;        }        もし (r < heap.個数 && heap[r] > heap[big])        {            big = r;        }        もし (big == i)        {            抜ける;        }        t = heap[big];        heap[big] = heap[i];        heap[i] = t;        i = big;    }    返す top;} // 정렬 기준: 마감이 이른 주문이 앞byDeadline(x, y){    返す x[1] - y[1];} n = コンソール.数読み()[0];jobs = []; // [걸리는 시간, 마감]繰り返す (i = 0; i < n; i++){    jobs.追加(コンソール.数読み());}jobs.並べ替え(byDeadline); chosen = []; // 고른 주문의 시간들(최대 힙)total = 0; // 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각それぞれ (job の中 jobs){    힙넣기(chosen, job[0]);    total += job[0];    もし (total > job[1])    {        total -= 힙꺼내기(chosen); // 마감을 넘으면 고른 것 가운데 가장 긴 주문을 뺀다    }}コンソール.書く(chosen.個数 + " " + total);