正经题解｜ 星球编号

题目解析

对于任意一个求星球在星系中是第几个被发现的，可以使用二分，对于前置位补 $0$，使用格式化输出就行 printf。

AC代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int t,n,m;
pair<int,int> a[N],b[N];
vector<int> v[N];
int main() {
    scanf("%d %d",&m,&n);
    map<int,int> mp;
    for(int i=0;i<n;i++) {
        scanf("%d %d",&a[i].first,&a[i].second);
        b[i].first = a[i].first;
        b[i].second = a[i].second;
    }
    sort(a,a+n);
    for(int i=0;i<n;i++) {
        auto j = a[i];
        v[j.first].push_back(j.second);
    }
    for(int i=0;i<n;i++) {
        auto j = b[i];
        int idx = lower_bound(v[j.first].begin(), v[j.first].end(),j.second) - v[j.first].begin() + 1;
        printf("%06d%06d\n",j.first,idx);
    }
    return 0;
}

复杂度

对于每一个星球都要进行一次二分，$(n \times log_n)$