B - Guidebook

GitHub跳转原题关系图返回列表

按城市名升序、分数降序排序后输出原始编号。

OJ: atcoder

题目 ID: abc128_b

难度:入门

标签:排序c++haskell

日期: 2026-07-10 21:42

目录

  1. 题意
  2. 思路
  3. 代码
  4. 代码
  5. 复杂度
  6. 总结

题意

按城市字典序升序、同城市按分数降序排列，输出餐厅编号。

思路

自定义排序：先城市名升序，同城市分数降序。

Haskell 中关键就这一句：

haskell
sorted = sortOn (\(city, score, _) -> (city, Down score)) restaurants

拆解：

  • restaurants 列表元素是三元组 (city, score, id)，如 ("kazan", 50, 3)
  • sortOn f 对每个元素计算 f 的值，然后按 f 的值升序排列
  • \(city, score, _) -> (city, Down score) 是一个 lambda，从三元组中提取 (city, Down score) 作为排序键
  • 先比 city：字符串按字典序升序（"kazan" < "khabarovsk" < "moscow"）
  • 再比 Down score：Down 包装后升序排列等价于原值降序（Down 50 < Down 35 因为 50 > 35）

所以 sortOn 先按城市名分组，同城市内按分数从高到低排列。

代码

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-10 21:42
 * update_at: 2026-07-10 21:42
 */
#include <bits/stdc++.h>
using namespace std;

struct Rest {
    string city;
    int score, id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector<Rest> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].city >> a[i].score;
        a[i].id = i + 1;
    }

    sort(a.begin(), a.end(), [](const Rest &x, const Rest &y) {
        if (x.city != y.city) return x.city < y.city;
        return x.score > y.score;
    });

    for (auto &r : a) cout << r.id << '\n';

    return 0;
}
haskell
{-
 Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 rainboy的学习导航网站: https://idx.roj.ac.cn
 create_at: 2026-07-10 22:00
 update_at: 2026-07-10 22:00
-}
import Data.List (sortOn)
import Data.Ord (Down(..))

type Restaurant = (String, Int, Int)  -- (city, score, index)

parseLine :: Int -> String -> Restaurant
parseLine i line =
    let [city, s] = words line
    in (city, read s, i)

main = do
    input <- getContents
    let (_:lns) = lines input
        restaurants = zipWith parseLine [1..] lns
        sorted = sortOn (\(city, score, _) -> (city, Down score)) restaurants
    mapM_ (print . (\(_,_,i) -> i)) sorted

复杂度

时间复杂度 O(Nlog⁡N)O(N \log N)，空间复杂度 O(N)O(N)。

总结

多关键字排序：sortOn (city, Down score)。