原题链接:Codeforces Round #743 (Div. 2)-B.Swaps
算法:排序
思路:1.很容易想到就是奇数数组和偶数数组,对偶数数组每一个遍历,找第一个奇数数组中比它小的又靠近数组最左端的,用双指针L遍历a,R遍历b,这样的答案就是L-1+R-1,然后一直更新答案;
2.由于t与n范围的限制我们显然不能两重循环,想办法去优化它。回到题目,奇数偶数的限制显然就是我们优化的破局点,2在b数组最左端时一定能找到1在a数组的下标,4找3或者1的。所以我们发现下标很重要,我们要存起来。
3.我们刚刚想到2找1,4找1或3,6找1或3或5,很明显我们肯定能找到,而且我们要找小于b数组那个偶数前面的那些奇数和它们对应的下标。在我们思考的过程中发现,我们这样想的话,a数组和b数组要有序,这样才好找,b数组某一个偶数前的所有奇数下标。
具体看代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],b[N],find_vi[2*N];
void solve()
{
memset(find_vi,0,sizeof find_vi);
int n; cin>>n;
//find_vi存下标,由value到index
for (int i=1;i<=n;i++) cin>>a[i],find_vi[a[i]]=i;
for (int i=1;i<=n;i++) cin>>b[i],find_vi[b[i]]=i;
sort(a+1,a+n+1); sort(b+1,b+n+1);
int ans=2*n;
int min_i=n;
for (int i=1;i<=n;i++)
{
min_i=min(min_i,find_vi[a[i]]); //在a数组中找最靠近最左端的下标;排序后已经实现了b数组中每一个位置都大于a数组,且a数组有序
ans=min(ans,find_vi[b[i]]-1+min_i-1);
}
cout<<ans<<endl;
}
int main ()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t; cin>>t;
while (t--) solve();
return 0;
}