Note：这个题无关Sort的稳定性问题，只是突然想起，不稳定排序的sor如何写cmp函数才变成稳定性排序，就是把return a1.value<=a2.value 写为return a1.value<a2.value即可，则相等不交换位置。
0
题目很清楚
1
每个数的归宿都是唯一的，第一个数组要变成第二个数组的样子，如果可以，那么每个数都对应唯一的正确位置，而位置就是1到n，所以每次输入一个调整的区间，就将该区间内的数sort。
2
#include <iostream> #include <stdio.h> #include <algorithm> using namespace std; const int maxn=1010; struct Nums{ int value; int pos; bool operator <(struct Nums nn)const{ return pos<nn.pos; } }num[maxn]; int b[maxn]; /* bool cmp(struct Nums a1,struct Nums a2){ return a1.value<a2.value; } */ int main() { //int a[]={5,4,3,2,1,0};sort(a+1,a+1+4,cmp);//a[]={5,1,2,3,4,0};两个参数分别是首地址和尾地址，其中尾地址是排序的最后一个数的下一个数的地址，有点左闭右开区间的意思。 //for(int i=0;i<=5;i++){cout<<a[i]<<" ";}cout<<endl; /* 如果cmp函数里是<则稳定排序，如果<=则不稳定排序 struct Nums test[maxn]; for(int i=0;i<=5;i++){ scanf("%d",&test[i].value); test[i].pos=i; } sort(test+1,test+1+4,cmp); for(int i=0;i<=5;i++){ cout<<test[i].pos<<endl; } */ int kase; cin>>kase; int n,m; while(kase--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&num[i].value); num[i].pos=-1; } for(int i=1;i<=n;i++){ scanf("%d",&b[i]); for(int j=1;j<=n;j++){ if(num[j].value==b[i]&&num[j].pos==-1){ num[j].pos=i; break;//一一对应，break } } } int l,r; for(int i=1;i<=m;i++){ scanf("%d%d",&l,&r); if(l>r) swap(l,r); sort(num+l,num+1+r);//a[]={5,4,3,2,1,0},sort(a+1,a+1+4);a[]={5,1,2,3,4,0}; } int flag=1; for(int i=1;i<=n;i++){ if(num[i].value!=b[i]){ flag=0; break; } } if(flag){ cout<<"Yes"<<endl; } else{ cout<<"No"<<endl; } } }
