题解 AT4738 [ABC128B] Guidebook

RBI_GL · 2021-04-09 20:14:38 · 题解

题意

题面

中文翻译已经的很清楚了。

思路

显然要进行排序。

为了方便操作，我们定义一个结构体，储存第 i 个餐厅的名字，分数和编号。

然后自己按照题意写一个 cmp 控制快排。

排序后输出第 i 个餐厅的编号即可。

时间复杂度为 \texttt{O(n log n)}。

Code:

#include <bits/stdc++.h>
using namespace std;
int n;
struct node {
    string s;
    int p;
    int id;
}a[1005];
bool cmp(node x, node y) { // 结构体排序 
    if (x.s == y.s) return x.p > y.p;
    else return x.s < y.s;
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) { //储存数据 
        cin >> a[i].s;
        scanf("%d", &a[i].p);
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; ++i) printf("%d\n", a[i].id);
    return 0;
}