good problem
Assumption is All You Need Gym - 103409D
题意：给两个长度为n < 2021的数列，两个数列都由1~n组成，能否由若干次操作使数列a变成b。一次操作是指：i < j 且 ai > aj，则可交换ai与aj的位置。若能则输出交换的过程。
`
`
`
`
思路：注意到每次操作都会使字典序减小。考虑一次ap与aq的交换，我们将aq交换到ap位置，必须得满足aq >= bp，(因为字典序只能减小，不能变大.)
对于aq，我们每次找最近的能与ap进行交换的aq,这样子能够保证字典序按最慢的速度减小。复杂度O(n*n)。
踩坑：
1.因为操作次数高达1e6，所以切记不能用endl，很慢，得用”\n”，不然数据大的时候就被卡了。
2.找aq的时候，不能每次都从p+1的位置开始往后找，其实只要从上次aq位置开始往后找即可，不然被卡。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=2222;
ll a[maxn],b[maxn];
ll n;
vector<P> ans;
void swap(ll i,ll j){
ll t=a[i];a[i]=a[j];a[j]=t;
ans.push_back({i,j});
}
void solve(){
for(ll i=1;i<=n;i++){
ll j=i;
while(a[i]!=b[i]){
if(a[i]<b[i]){
cout<<"-1"<<endl;return ;
}
j++;
for(;j<=n;j++){
if(a[i]>=a[j] && a[j]>=b[i]) break;
}
swap(i,j);
}
}
cout<<ans.size()<<endl;
for(auto i=ans.begin();i!=ans.end();i++){
cout<<(*i).first<<" "<<(*i).second<<"\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll ca;cin>>ca;
while(ca--){
ans.clear();
cin>>n;
for(ll i=1;i<=n;i++) cin>>a[i];
for(ll i=1;i<=n;i++) cin>>b[i];
solve();
}
return 0;
}
|