2025-09-22 学习日记

	class MovieRentingSystem {
	    //解决search
	    //需要一个map,键为movie,值为一个集合装pair<shop,price>,要去重使用set
	    unordered_map<int,set<pair<int,int>>> movie_sh_pr;
	    //需要一个能去重的容器来储存所有的数据
	    set<tuple<int,int,int>> st;
	    //哈希值类型存储实现
	    unordered_map<long long,int> hashmp;
	public:
	    //有n个商店
	    MovieRentingSystem(int n, vector<vector<int>>& entries) {
	        for(auto &e:entries){
	            int shop = e[0],movie = e[1],price = e[2];
	            hashmp[1LL*shop<<32 | movie] = price;
	            movie_sh_pr[movie].emplace(price,shop);
	        }
	    }
	    //要一个容器来对价格进行排序,价格相同shop小在前
	    //返回5个商店shop
	    vector<int> search(int movie) {
	        //要获得前5个shop,找到排在最后的movie位置,如果不足5个照样输出
	        auto it = movie_sh_pr.find(movie);
	        //如果没找到就返回空
	        if(it==movie_sh_pr.end()) return {};
	        vector<int> ans;//装答案
	        for(auto &[_,shop]:it->second){
	            ans.push_back(shop);
	            if(ans.size()==5) break;
	        }
	        return ans;
	    }
	    //指定商店查找电影,保证存在
	    //如果使用一个集合来装movie和price对,那么每次都要查询shop和movie,双查询显然是不行的
	    //商店是明显不同但是可以直接map快速查找,问题在不同的电影有不同的价格,要查找电影找到价格
	    //商店->电影->价格,我们可以直接同时查找商店和电影,有个小技巧,就是利用哈希值将商店和电影捆绑在一起
	    //把shop左移到int的最大,即把long long分成两个部分,两个int类型的部分,long是2^64,就是两个2^32,前2^32存shop,后2^32存电影,这样一个大整数就可以存储两个值了
	    void rent(int shop, int movie) {
	        int price = hashmp[1LL*shop<<32|movie];
	        //删除对应的电影
	        movie_sh_pr[movie].erase({price,shop});
	        st.emplace(price,shop,movie);
	    }
	    //查找商店,返还之前的指定电影
	    //注意erase无论用多少次都是log(n),所以可以放心删除
	    void drop(int shop, int movie) {
	        int price = hashmp[1LL*shop<<32|movie];
	        movie_sh_pr[movie].emplace(price,shop);
	        st.erase({price,shop,movie});
	    }
	    //返回最便宜的5部已经借出的电影(包括重复),不返回价格
	    //价格升序,shop小的在前,movie小的在前
	    vector<vector<int>> report() {
	        vector<vector<int>> ans;
	        for(auto&[_,shop,movie]:st){
	            ans.push_back({shop,movie});
	            if(ans.size()==5) break;
	        }
	        return ans;
	    }
	};