思路:
把a,b数组开成pair,first存值,second存下标,然后把两个数组排序,由于在同一位置下,a数组永远小于b数组,所以我们每到一个位置,就取一个min的dist(a[i]到开头的距离),保证a[i]的位置尽量靠前,然后再取一个min的res,由于下标从1开始,所以res取最小的b.second + dist - 2
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cmath> using namespace std; typedef pair<int, int>PII; typedef long long LL; const int N = 100010; PII a[N], b[N]; int main() { int T; cin >> T; while (T--) { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i].first, a[i].second = i; for (int i = 1; i <= n; i++) cin >> b[i].first, b[i].second = i; sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + n); int dist = 0x3f3f3f3f, res = 0x3f3f3f3f; for (int i = 1; i <= n; i++) { dist = min(dist, a[i].second);//随着i的增加,a[i]要保证位置要尽量靠前 res = min(res, b[i].second + dist - 2); } cout << res << endl; } return 0; } //3(1) 1(2) //4(1) 2(2) // //1(2) 3(1) //2(2) 4(1) // //7(1) 5(2) 9(3) 1(4) 3(5) //2(1) 4(2) 6(3) 10(4) 8(5) // //1(4) 3(5) 5(2) 7(1) 9(3) //2(1) 4(2) 6(3) 8(5) 10(4)