LC.2353 ｜ 设计食物评分系统 ｜ 有序集合 ｜ 负分数排序实现“最高分优先 + 字典序优先”
输入：
FoodRatings(foods, cuisines, ratings)：初始化 n 种食物changeRating(food, newRating)：修改某个食物评分highestRated(cuisine)：查询某种烹饪方式下评分最高的食物（若并列取字典序更小）
要求：
- 评分最高优先
- 评分相同按字典序最小优先
- 支持多次修改与查询
输出：
highestRated返回食物名
思路：
这题核心就是维护两个维度的信息：
1）食物 -> (菜系, 当前评分)
用unordered_map<string, pair<string,int>> food_info存：
- 方便
changeRating(food, ...)时，O(1) 找到它属于哪个菜系 + 旧评分是多少。
2）菜系 -> 一棵有序结构，能随时拿到“最强的那个”
用unordered_map<string, set<pair<int,string>>> cuisine_ratings存：
- 每个菜系一个
set，里面放(-rating, food)这样的二元组。 set默认按 pair 从小到大排序：-rating越小，代表rating越大（最高分排最前）- 若
-rating相同，就比较food字符串（字典序小的排前）
- 所以
highestRated(cuisine)直接返回begin()->second即可。
changeRating 怎么做？
对一个食物：
- 从
food_info取出它的cuisine和oldRating - 在对应
set里删除旧键(-oldRating, food) - 插入新键
(-newRating, food) - 更新
food_info[food].second = newRating
这样能保证每次修改后，菜系的“冠军”始终在set.begin()。
复杂度：
- 时间复杂度：
- 初始化：O(N log N)（每次插入 set）
changeRating：O(log M)（M 为该 cuisine 下食物数）highestRated：O(1)（取 begin）
- 空间复杂度：O(N)
classFoodRatings{private:unordered_map<string,pair<string,int>>food_info;unordered_map<string,set<pair<int,string>>>cuisine_ratings;public:FoodRatings(vector<string>&foods,vector<string>&cuisines,vector<int>&ratings){for(inti=0;i<(int)foods.size();++i){food_info[foods[i]]={cuisines[i],ratings[i]};cuisine_ratings[cuisines[i]].insert({-ratings[i],foods[i]});}}voidchangeRating(string food,intnewRating){auto&info=food_info[food];string cuisine=info.first;intoldRating=info.second;cuisine_ratings[cuisine].erase({-oldRating,food});cuisine_ratings[cuisine].insert({-newRating,food});info.second=newRating;}stringhighestRated(string cuisine){returncuisine_ratings[cuisine].begin()->second;}};