小明的账单

题目描述

小明每天收到若干账单。每天需从尚未支付的账单中取出面额最小和最大的两张付清，未付账单累积到下一天。输入天数 $N$ 和每天收到的账单，输出每天支付的两个面额（先小后大）。每天保证至少能支付两张。

思路

把未付账单看成一个可重集合，每天只需插入新账单并取删最小、最大两个元素，用 multiset 即可在 $O(\log K)$ 内完成每个操作。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 07:30
# update_at: 2026-09-30 07:30

import sys
from collections import Counter
from heapq import heappop, heappush


def clean_top(heap: list[int], cnt: Counter[int]) -> None:
    """反复弹出已付清面额的堆顶，直到堆顶是池里还没付的账单。"""
    while cnt[abs(heap[0])] == 0:  # 账单付掉时只减计数，堆里留到此刻才真正删除
        heappop(heap)


def pay_extremes(lo: list[int], hi: list[int], cnt: Counter[int]) -> tuple[int, int]:
    """付出账单池里面额最小和最大的两张，返回这两个面额。"""
    clean_top(lo, cnt)
    clean_top(hi, cnt)
    low, high = lo[0], -hi[0]  # hi 存相反数，取负还原面额
    cnt[low] -= 1
    cnt[high] -= 1
    return low, high


def solve() -> None:
    inp = sys.stdin.buffer.readline
    n = int(inp())               # 补卡天数
    cnt: Counter[int] = Counter()  # 面额 -> 未支付张数（懒删除的记账本）
    lo: list[int] = []           # 面额小根堆
    hi: list[int] = []           # 面额相反数的小根堆，即面额大根堆
    out: list[str] = []

    for _ in range(n):
        parts = inp().split()
        m = int(parts[0])        # 当天新增账单数
        for v in map(int, parts[1:m + 1]):
            cnt[v] += 1
            heappush(lo, v)
            heappush(hi, -v)
        low, high = pay_extremes(lo, hi, cnt)
        out.append(f'{low} {high}')

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:23
 * update_at: 2026-10-05 12:23
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n, m, x;
multiset<ll> s; // 未支付账单的多重集合

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> m;
        for (ll j = 1; j <= m; j++) {
            cin >> x;
            s.insert(x);
        }
        // 取出并删除最小和最大两张（不同账单，面额可相同）
        multiset<ll>::iterator it_min = s.begin();
        multiset<ll>::iterator it_max = prev(s.end());
        ll low = *it_min;
        ll high = *it_max;
        cout << low << " " << high << "\n";
        s.erase(it_min);
        // 若最小和最大指向同一元素，删除后再取最大会失效，需重新定位
        if (it_max == it_min) {
            it_max = prev(s.end());
        }
        s.erase(it_max);
    }
    return 0;
}

目录

题目描述

思路

参考代码