- 进行排序的运算符必须满足严格弱序(满足传递性和不可比性的传递性)
- 按逆序对数排序显然不满足不可比性的传递性,如(1,5)(3,3)(2,6)
- 同一个组内的两个数的相对大小不影响答案,应该猜想按较小值排序
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int a[100005][2];
int ord[100005];
bool cmp(int u,int v)
{return min(a[u][0],a[u][1])<min(a[v][0],a[v][1])||min(a[u][0],a[u][1])==min(a[v][0],a[v][1])&&max(a[u][0],a[u][1])<max(a[v][0],a[v][1]);
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int T;cin>>T;while(T--){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i][0]>>a[i][1];ord[i]=i;}sort(ord+1,ord+n+1,cmp);for(int i=1;i<n;i++){cout<<a[ord[i]][0]<<" "<<a[ord[i]][1]<<" ";}cout<<a[ord[n]][0]<<" "<<a[ord[n]][1]<<endl;}return 0;
}