Problem: Music Game 题解

读题可知，n个音符的区别在于所在路线编号不同，以及到达判定线的时间不同。要想知道音符的击打顺序，只需要将这些音符按照时间排序即可。注意，由于数据量较大，需要使用时间复杂度为O（nlogn）的算法排序，如归并排序、快速排序，这里推荐库函数sort。但是，我要怎么知道排序后第一个输出的音符在编号为几的路线上呢？这就需要我们在排序的时候，把音符和它所在的路线编号绑在一起，这样可以达到排序后O（1）读取所在路线编号的目的，而这种方法即为结构化绑定，具体体现为用一个结构体表示一个音符到达判定线的时间以及其所在路线的编号。 如果需要使用sort并且进行了结构化绑定操作，则需要重载sort中的cmp函数，详见代码。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

struct Node{
    ll x;int num;
};

bool my_cmp(Node &a,Node &b)
{
    return a.x==b.x?a.num<b.num:a.x<b.x;
}

int main()
{
    int n;
    cin>>n;
    Node a[n];
    for(int i=0;i<n;i++) cin>>a[i].x>>a[i].num;
    sort(a,a+n,my_cmp);
    for(int i=0;i<n;i++) cout<<a[i].num<<" ";
    return 0;
}