你正在开发一款名叫“小众点评”的软件,其中有N家餐厅,你需要对这些餐厅进行排序, 第i家餐厅位于的城市名为字符串S i ,评分为 pi 。 现在用户希望按照城市的字典序排序,如果有多家餐厅在同一个城市,则按餐厅的评分排序。输出每家餐厅在输入时的原下标 #include<bits/stdc++.h> using namespace std; vector< pair< string,pair<int,int> > >vec;//城市,评分,id int n; int main(){ cin>>n; for(int i=0;i<n;i++) { string s; int a; cin>>s>>a; vec.push_back({s,{-a,i}});//-a为了从大到小排序 } sort(vec.begin(),vec.end()); for(int i=0;i<n;i++) cout<<vec[i].second.second<<endl; return 0; }解释下,是否城市,评分,id 3个参数的排序用pair必须是这种方式:vector< pair< string,pair<int,int> > >vec;
时间: 2025-03-12 20:21:00 浏览: 38
在这个场景中,我们的确可以使用`pair`来存储城市、评分以及原始下标,并通过内置的排序函数来进行排序。下面详细解释一下为什么要这么做及是否有其他替代方案。
### 解释当前方式
给定的数据结构 `vector<pair<string, pair<int, int>>> vec;` 中:
- 第一层`string`用于保存每个餐馆所属的城市名。
- 内层的第一个`int`(-a)表示的是该餐馆的得分(取负数是为了让标准升序排列成为降序)。
- 内层第二个`int`(i)则是记录了这个餐馆原本的位置索引。
这样做有几个优点:
1. **简洁**:只需要一行数据就能表达三个属性;
2. **高效**:由于C++ STL库对复合类型的默认比较规则是从左至右依次检查元素之间的大小关系,因此可以直接利用这一点完成题目所描述的需求——先按城市名称字典顺序排,再在同一城市的内部根据分数高低逆向排;
```cpp
// 排序时会首先依据第一项(即城市),然后对于相同城市的项目将基于第二项中的第一个值(这里是-a)
sort(vec.begin(), vec.end()); // 使用默认小于操作符(<),自动实现所需功能。
```
### 其他可行的方式?
当然还有别的方法能够达成同样的效果:
#### 方式一:自定义结构体+Comparator
你可以创建一个包含这三个字段的小型结构体,并为其提供一个适当的构造函数和比较运算符重载版本。
```cpp
struct RestaurantInfo {
string city;
int score;
int originalIndex;
bool operator<(const RestaurantInfo &other)const{
if (city != other.city){
return city < other.city;
}
else{ // 如果两个饭店属于同一个城市,则按分数从高到底排序
return score > other.score;
}
}
};
// 然后改用此结构体代替原来的pair组合形式...
std::vector<RestaurantInfo> restaurantsVec(n);
for(int i = 0 ; i < n ; ++i){
cin >> restaurantsVec[i].city >> restaurantsVec[i].score;
restaurantsVec[i].originalIndex = i + 1;
}
// 直接调用 sort 函数即可正常使用 Comparator 进行正确的排序
sort(restaurantsVec.begin(),restaurantsVec.end());
```
#### 方式二:直接修改已有pair方案下的比较逻辑
如果你坚持沿用最开始提供的基于`pair`的方式来处理这个问题的话,也可以考虑在排序阶段指定特定的比较准则而不是依赖于默认的行为:
```cpp
bool cmp(const pair<string, pair<int,int>>& a,const pair<string, pair<int,int>>& b){
if(a.first == b.first){ // 同城内按分倒序
return -a.second.first>b.second.first;
}else{// 按市正序
return a.first<b.first;
}
}
...
sort(begin(vec), end(vec),cmp);
```
这种方式同样能解决问题,而且保持了原有的`pair`结构不变。
综上所述,在你给出的例子中使用的`pair`确实是一种合理而有效的方法之一,但它并不是唯一的解决方案。选择哪种取决于个人偏好、代码复杂度等因素。
阅读全文
相关推荐












