题解 | #餐馆#

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

// 客人结构体
struct Guest {
    int num;    // 人数
    int money;  // 消费金额
};

// 按消费金额降序排序
bool cmp(Guest a, Guest b) {
    if(a.money == b.money) return a.num < b.num;
    return a.money > b.money;
}

int main() {
    int n, m;
    while(cin >> n >> m) {
        // 读入桌子容量
        multiset<int> tables;
        for(int i = 0; i < n; i++) {
            int capacity;
            cin >> capacity;
            tables.insert(capacity);
        }
        
        // 读入客人信息
        vector<Guest> guests(m);
        for(int i = 0; i < m; i++) {
            cin >> guests[i].num >> guests[i].money;
        }
        
        // 按消费金额排序
        sort(guests.begin(), guests.end(), cmp);
        
        // 安排座位
        long long total = 0;
        for(int i = 0; i < m; i++) {
            if(tables.empty()) break;
            
            // 找到能容纳的最小桌子
            auto it = tables.lower_bound(guests[i].num);
            if(it != tables.end()) {
                total += guests[i].money;
                tables.erase(it);
            }
        }
        
        cout << total << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    // 客人类
    static class Guest {
        int num, money;
        Guest(int num, int money) {
            this.num = num;
            this.money = money;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            
            // 读入桌子容量
            TreeMap<Integer, Integer> tables = new TreeMap<>();
            for(int i = 0; i < n; i++) {
                int capacity = sc.nextInt();
                tables.put(capacity, tables.getOrDefault(capacity, 0) + 1);
            }
            
            // 读入客人信息
            Guest[] guests = new Guest[m];
            for(int i = 0; i < m; i++) {
                guests[i] = new Guest(sc.nextInt(), sc.nextInt());
            }
            
            // 按消费金额排序
            Arrays.sort(guests, (a, b) -> {
                if(a.money != b.money) return b.money - a.money;
                return a.num - b.num;
            });
            
            // 安排座位
            long total = 0;
            for(Guest g : guests) {
                Map.Entry<Integer, Integer> entry = tables.ceilingEntry(g.num);
                if(entry != null) {
                    total += g.money;
                    if(entry.getValue() == 1) {
                        tables.remove(entry.getKey());
                    } else {
                        tables.put(entry.getKey(), entry.getValue() - 1);
                    }
                }
            }
            
            System.out.println(total);
        }
    }
}

from typing import List
import bisect
from collections import Counter

def max_revenue(n: int, m: int, tables: List[int], guests: List[List[int]]) -> int:
    # 将桌子容量排序
    tables.sort()
    
    # 将客人按消费金额降序排序
    guests.sort(key=lambda x: (-x[1], x[0]))
    
    # 使用Counter来模拟multiset
    table_count = Counter(tables)
    available_tables = sorted(table_count.keys())
    
    total = 0
    for num, money in guests:
        # 找到能容纳的最小桌子
        idx = bisect.bisect_left(available_tables, num)
        if idx < len(available_tables):
            table_size = available_tables[idx]
            total += money
            table_count[table_size] -= 1
            if table_count[table_size] == 0:
                available_tables.pop(idx)
    
    return total

def main():
    while True:
        try:
            n, m = map(int, input().split())
            tables = list(map(int, input().split()))
            guests = []
            for _ in range(m):
                num, money = map(int, input().split())
                guests.append([num, money])
            print(max_revenue(n, m, tables, guests))
        except EOFError:
            break

if __name__ == "__main__":
    main()