AtCoder题解｜ABC 113C ID

题目信息 📚

【题目描述】

In the Republic of Atcoder, there are $N$ prefectures, and a total of $M$ cities that belong to those prefectures.

City $i$ is established in year $Y_i$ and belongs to Prefecture $P_i$.

You can assume that there are no multiple cities that are established in the same year.

It is decided to allocate a $12$-digit ID number to each city.

If City $i$ is the $x$-th established city among the cities that belong to Prefecture $i$, the first six digits of the ID number of City $i$ is $P_i$, and the last six digits of the ID number is $x$.

Here, if $P_i$ or $x$ (or both) has less than six digits, zeros are added to the left until it has six digits.

Find the ID numbers for all the cities.

Note that there can be a prefecture with no cities.

【输入】

The input is given from Standard Input in the following format:

$N$ $M$

$P_1$ $Y_1$

$\vdots$

$P_M$ $Y_M$

【输出】

Print the ID numbers for all the cities, in ascending order of indices (City 1, City 2, …).

【数据范围】

$1 \leq N \leq 10^5$
$1 \leq M \leq 10^5$
$1 \leq P_i \leq N$
$1 \leq Y_i \leq 10^9$
$Y_i$ are all different.

All values in the input are integers.

【输入样例1】

【输出样例1】

000001000002
000002000001
000001000001

As City 1 is the second established city among the cities that belong to Prefecture 1, its ID number is 000001000002.
As City 2 is the first established city among the cities that belong to Prefecture 2, its ID number is 000002000001.
As City 3 is the first established city among the cities that belong to Prefecture 1, its ID number is 000001000001.

【输入样例2】

【输出样例2】

000002000001
000002000002
000002000003

【题目来源】

https://atcoder.jp/contests/abc113/tasks/abc113_c

题目解析 🍉

【题目分析】

法一：自定义数据结构 + 多级排序 + 自定义函数实现前缀零（模拟题）

优化版：二维 vector 存数据 + 排序 + printf 实现前缀零

【C++代码】

模拟 + 多级排序 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
typedef struct City {  // 自定义一个City的数据结构
    int p;  // City所属的prefecture
    int y;  // City的年份
    int order;  // City读入序号
    string id;  // City输出编号
} City;
City cities[N];

// 按照城市所属prefeture以及年份排序
bool cmp1(City a, City b) {
    if (a.p == b.p) return a.y < b.y;
    else return a.p < b.p;
}

// 按照城市输入顺序排序
bool cmp2(City a, City b) {
    return a.order < b.order;
}

// 添加前缀
string add_zero(int x) {
    string s = "";
    string t = to_string(x);
    for (int i = 1; i <= 6 - t.size(); i++) s += "0";
    s += t;
    return s;
}

int main() {
    // 读入m个城市
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int p, y;
        cin >> p >> y;
        cities[i].order = i;
        cities[i].p = p;
        cities[i].y = y;
    }
    // 按照所属prefectures以及年份排序
    sort(cities + 1, cities + 1 + m, cmp1);

    // 分配所有编号
    int cnt = 1;  // 城市序号
    for (int i = 1; i <= m; i++) {
        // 分配编号
        string id = add_zero(cities[i].p);
        id += add_zero(cnt++);
        cities[i].id = id;

        // 新的prefecture，序号更新
        if (cities[i].p != cities[i + 1].p) cnt = 1;
    }

    // 按照输入顺序重新排序，输出编号
//    sort(cities + 1, cities + 1 + m, cmp2);
    // 定义匿名函数替代cmp2
    sort(cities + 1, cities + 1 + m, [](auto a, auto b) { return a.order < b.order; });
    for (int i = 1; i <= m; i++) cout << cities[i].id << endl;

    return 0;
}

简化版 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m, p[N], y[N];
vector<int> v[N];

int main() {
    // 读入m个城市
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &p[i], &y[i]);
        v[p[i]].push_back(y[i]);
    }

    // 对prefetures按照年份排序
    for (int i = 0; i < N; i++) {
        sort(v[i].begin(), v[i].end());
    }

    // 按照输入顺序，查询每个城市在所属prefecture中的顺序
    for (int i = 1; i <= m; i++) {
        // 利用lower_bound查询
        int id = lower_bound(v[p[i]].begin(), v[p[i]].end(), y[i]) - v[p[i]].begin() + 1;
        // 前缀零通过printf实现
        printf("%06d%06d\n", p[i], id);
    }

    return 0;
}