题解 AT4738 【[ABC128B] Guidebook】

Zirnc · 2020-03-03 11:19:04 · 题解

ChungZH's blog · ChungZH's portfolio

题目

您已决定写一本介绍美食餐厅的书，您要介绍 N 家餐厅：餐厅 1，餐厅 2，...，餐厅 N。餐厅 i 在城市 S_i 中，您对餐厅 i 的评估得分为 P_i（ 100 分制）。没有两家餐厅的分数相同。

您要按以下顺序介绍餐厅：

• 这些餐厅按其城市名称的字典顺序排列。
• 如果在同一城市中有多个餐厅，则它们按照得分的降序排列。

按照书中介绍的顺序打印餐厅的识别号。

题解

这道题很简单，用结构体+自定义排序函数的套路就好了。

排序函数：

1. 如果是不同城市，就比较城市名的大小（按字典序）。
2. 如果是相同城市，就比较分数。

结构体里还要记得计一个识别号（i）。

代码里省略了很多内容，抄不了的啦~

···
struct restaurant {
  string cityn;
  int score;
  int index; // 识别号
} a[103]; 
bool cmp(restaurant x, restaurant y) {
  if (x.cityn != y.cityn) {
    return x.cityn < y.cityn;
  }
  return x.score > y.score;
}
int main() {
  ···
  for (int i = 1; i <= N; i++) {
    cin >> a[i].cityn >> a[i].score;
    a[i].index = i;
  }

  sort(a + 1, a + 1 + N, cmp);

  ···
}