题目

你有一个电影租借公司和 n 个电影商店。你想要实现一个电影租借系统，它支持查询、预订和返还电影的操作。同时系统还能生成一份当前被借出电影的报告。

所有电影用二维整数数组 entries 表示，其中 entries[i] = [shopi, moviei, pricei] 表示商店 shopi 有一份电影 moviei 的拷贝，租借价格为 pricei 。每个商店有 至多一份 编号为 moviei 的电影拷贝。

系统需要支持以下操作：

Search：找到拥有指定电影且 未借出 的商店中 最便宜的 5 个 。商店需要按照价格升序排序，如果价格相同，则 shopi 较小的商店排在前面。如果查询结果少于 5 个商店，则将它们全部返回。如果查询结果没有任何商店，则返回空列表。
Rent：从指定商店借出指定电影，题目保证指定电影在指定商店 未借出 。
Drop：在指定商店返还 之前已借出 的指定电影。
Report：返回 最便宜的 5 部已借出电影 （可能有重复的电影 ID），将结果用二维列表 res 返回，其中 res[j] = [shopj, moviej] 表示第 j 便宜的已借出电影是从商店 shopj 借出的电影 moviej 。res 中的电影需要按价格升序排序；如果价格相同，则 shopj 较小的排在前面；如果仍然相同，则 moviej 较小的排在前面。如果当前借出的电影小于 5 部，则将它们全部返回。如果当前没有借出电影，则返回一个空的列表。

请你实现 MovieRentingSystem 类：

MovieRentingSystem(int n, int[][] entries) 将 MovieRentingSystem 对象用 n 个商店和 entries 表示的电影列表初始化。
List<Integer> search(int movie) 如上所述，返回 未借出 指定 movie 的商店列表。
void rent(int shop, int movie) 从指定商店 shop 借出指定电影 movie 。
void drop(int shop, int movie) 在指定商店 shop 返还之前借出的电影 movie 。
List<List<Integer>> report() 如上所述，返回最便宜的 已借出 电影列表。

注意：测试数据保证 rent 操作中指定商店拥有 未借出 的指定电影，且 drop 操作指定的商店 之前已借出 指定电影。

示例 1：

输入： ["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"] [[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]] 输出： [null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]

解释： MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]); movieRentingSystem.search(1); // 返回 [1, 0, 2] ，商店 1，0 和 2 有未借出的 ID 为 1 的电影。商店 1 最便宜，商店 0 和 2 价格相同，所以按商店编号排序。 movieRentingSystem.rent(0, 1); // 从商店 0 借出电影 1 。现在商店 0 未借出电影编号为 [2,3] 。 movieRentingSystem.rent(1, 2); // 从商店 1 借出电影 2 。现在商店 1 未借出的电影编号为 [1] 。 movieRentingSystem.report(); // 返回 [[0, 1], [1, 2]] 。商店 0 借出的电影 1 最便宜，然后是商店 1 借出的电影 2 。 movieRentingSystem.drop(1, 2); // 在商店 1 返还电影 2 。现在商店 1 未借出的电影编号为 [1,2] 。 movieRentingSystem.search(2); // 返回 [0, 1] 。商店 0 和 1 有未借出的 ID 为 2 的电影。商店 0 最便宜，然后是商店 1 。

提示：

1 <= n <= 3 * 10^5
1 <= entries.length <= 10^5
0 <= shopi < n
1 <= moviei, pricei <= 10^4
每个商店至多有一份电影 moviei 的拷贝。
search，rent，drop 和 report 的调用总共不超过 10^5 次。

解题思路

1. 核心需求分析

我们先分解每个操作需要什么：

search(movie):
- 对象: 特定 movie 的未借出拷贝。
- 操作: 查找最便宜的 5 个。
- 排序规则: 1. 按 price 升序；2. 若 price 相同，按 shop 升序。
report():
- 对象: 所有已借出的电影。
- 操作: 查找最便宜的 5 部。
- 排序规则: 1. 按 price 升序；2. 若 price 相同，按 shop 升序；3. 若前两者还相同，按 movie 升序。
rent(shop, movie):
- 操作: 将一个电影的状态从“未借出”变为“已借出”。这是一个状态转移操作。
drop(shop, movie):
- 操作: 将一个电影的状态从“已借出”恢复为“未借出”。这也是一个状态转移操作。

2. 关键挑战与设计思路

状态管理: 系统中的每一份电影拷贝 (shop, movie) 都有两种状态：未借出 (available) 和 已借出 (rented)。rent 和 drop 操作就是在两个状态之间移动电影。
高效排序查询: search 和 report 都要求返回“最便宜的 5 个”，这意味着我们需要的数据结构必须能够快速访问到排序后的结果。每次操作都进行全局排序是不可接受的，效率太低。因此，我们需要能够自动维护排序的数据结构。

基于以上分析，我们可以设计以下数据结构来分别管理两种状态的电影，并满足各自的查询需求。

3. 数据结构的选择

我们将使用三个主要的数据结构：

一个哈希表，用于存储电影的基本信息 (价格)
- 结构: map<pair<int, int>, int>，即 (shop, movie) -> price。
- 作用: 当我们知道一个 (shop, movie) 组合时，可以快速（O(1) 平均时间）查到它的价格。这在 rent 和 drop 操作中非常有用，因为我们需要根据价格来更新其他数据结构。我们称之为 prices。
一个数据结构，用于管理所有“未借出”的电影
- 需求: 需要按 movie 分组，并且在每个分组内按 (price, shop) 排序。
- 结构: map<int, set<pair<int, int>>>。
  - 外层 map 的键 (Key): movie ID。
  - 外层 map 的值 (Value): 一个 set 集合。
  - 内层 set 的元素: pair<int, int>，即 {price, shop}。
- 为什么用 set?: set 是一个有序集合（通常用红黑树实现），它能自动对插入的元素进行排序。pair 的默认比较方式是先比较第一个元素，如果相同再比较第二个，这完美符合 search 操作的排序规则 (price, shop)。
- 命名: 我们称之为 available_movies。
- search(movie) 操作: 只需访问 available_movies[movie] 这个 set，然后按顺序取出前 5 个元素即可。由于 set 内部有序，这个过程非常快。
一个数据结构，用于管理所有“已借出”的电影
- 需求: 需要存储所有已借出的电影，并按 (price, shop, movie) 全局排序。
- 结构: set<tuple<int, int, int>>。
  - set 的元素: tuple<int, int, int>，即 {price, shop, movie}。
- 为什么用 set<tuple>?: tuple 的默认比较方式也是逐个元素比较，这完美符合 report 操作的排序规则 (price, shop, movie)。这个 set 会自动维护所有已借出电影的全局排序。
- 命名: 我们称之为 rented_movies。
- report() 操作: 只需访问这个 set，然后按顺序取出前 5 个元素即可。

4. 各方法实现逻辑

现在我们把这些数据结构串联起来，看看每个方法具体如何工作。

MovieRentingSystem(n, entries) (构造函数)

遍历 entries 数组中的每一条记录 [shop, movie, price]。
将电影的价格存入 prices 哈希表：prices[{shop, movie}] = price。
由于初始时所有电影都未借出，将它们全部加入 available_movies：available_movies[movie].insert({price, shop})。

search(int movie)

在 available_movies 中找到 movie 对应的 set。
遍历这个 set（它已经按 price 和 shop 排序好了）。
取出前 5 个元素的 shop ID，存入结果列表并返回。

时间复杂度: O(log K)，其中 K 是拥有该电影的商店数量。主要是查找 map 和 set 的开销，遍历前 5 个是常数时间。

rent(int shop, int movie)

从 prices 哈希表中查出价格 price = prices[{shop, movie}]。
从 available_movies 中移除这部电影：available_movies[movie].erase({price, shop})。
将这部电影的信息加入 rented_movies 集合：rented_movies.insert({price, shop, movie})。

时间复杂度: O(log K + log R)，其中 K 是拥有该电影的商店数量，R 是已租借电影总数。主要是两个 set 的操作开销。

drop(int shop, int movie)

从 prices 哈希表中查出价格 price = prices[{shop, movie}]。
从 rented_movies 集合中移除这部电影：rented_movies.erase({price, shop, movie})。
将这部电影重新加入 available_movies：available_movies[movie].insert({price, shop})。

时间复杂度: O(log K + log R)，同 rent。

report()

遍历 rented_movies 这个全局有序集合。
取出前 5 个元组 {price, shop, movie}。
将每个元组的 shop 和 movie 存入结果列表 [[shop1, movie1], [shop2, movie2], ...] 并返回。

时间复杂度: O(1) （遍历前 5 个元素是常数时间）。

这个设计思路的核心是用多个专用数据结构来分别处理不同的业务逻辑，而不是试图用一个万能的数据结构解决所有问题。通过将电影按“未借出”和“已借出”两个状态池进行分离管理，并为每个池子选择能够自动维护其特定排序规则的 set 结构，我们大大简化了查询操作的复杂度，将它们从潜在的 O(N log N) 排序降至了高效的 O(log N) 甚至 O(1) 级别。

具体代码

class MovieRentingSystem {
private:
    // 结构 1: 快速查找 (shop, movie) -> price
    // 使用 std::map 是因为 std::pair 没有默认的哈希函数给 unordered_map 使用
    std::map<std::pair<int, int>, int> prices;

    // 结构 2: 管理未借出的电影
    // movie_id -> set of {price, shop}
    // set 会自动按 price, shop 排序
    std::map<int, std::set<std::pair<int, int>>> available_movies;

    // 结构 3: 管理已借出的电影，全局按 price, shop, movie 排序
    // set of {price, shop, movie}
    std::set<std::tuple<int, int, int>> rented_movies;

public:
    /**
     * @brief 构造函数，初始化系统
     */
    MovieRentingSystem(int n, std::vector<std::vector<int>>& entries) {
        for (const auto& entry : entries) {
            int shop = entry[0];
            int movie = entry[1];
            int price = entry[2];

            // 存入价格信息
            prices[{shop, movie}] = price;
            // 初始时，所有电影都可借
            available_movies[movie].insert({price, shop});
        }
    }
    
    /**
     * @brief 查找拥有指定电影且未借出的最便宜的5个商店
     */
    std::vector<int> search(int movie) {
        std::vector<int> result;
        if (available_movies.find(movie) == available_movies.end()) {
            return result; // 没有这部电影
        }

        auto& available_shops = available_movies.at(movie);
        int count = 0;
        // 遍历已按 {price, shop} 排序的 set
        for (const auto& pair : available_shops) {
            if (count >= 5) {
                break;
            }
            result.push_back(pair.second); // pair.second 是 shop
            count++;
        }
        return result;
    }
    
    /**
     * @brief 从指定商店借出电影
     */
    void rent(int shop, int movie) {
        // 1. 查找价格
        int price = prices.at({shop, movie});

        // 2. 从 "available" 池中移除
        available_movies.at(movie).erase({price, shop});

        // 3. 加入到 "rented" 池中
        rented_movies.insert({price, shop, movie});
    }
    
    /**
     * @brief 返还电影
     */
    void drop(int shop, int movie) {
        // 1. 查找价格
        int price = prices.at({shop, movie});

        // 2. 从 "rented" 池中移除
        rented_movies.erase({price, shop, movie});

        // 3. 加回到 "available" 池中
        available_movies[movie].insert({price, shop});
    }
    
    /**
     * @brief 报告最便宜的5部已借出电影
     */
    std::vector<std::vector<int>> report() {
        std::vector<std::vector<int>> result;
        int count = 0;
        // 遍历已按 {price, shop, movie} 全局排序的 set
        for (const auto& t : rented_movies) {
            if (count >= 5) {
                break;
            }
            // std::get<index>(tuple) 用于获取元组元素
            result.push_back({std::get<1>(t), std::get<2>(t)}); // {shop, movie}
            count++;
        }
        return result;
    }
};

1912. 设计电影租借系统

beautifulremi

题目