伊犁哈萨克自治州网站建设_网站建设公司_阿里云_seo优化

输入：

• 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 怎么做？

对一个食物：

1. 从food_info取出它的cuisine和oldRating
2. 在对应set里删除旧键(-oldRating, food)
3. 插入新键(-newRating, food)
4. 更新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;}};