势能就是i + a[i],很有用的结论 对于能完成交换，从A变成B，势能数组一定相同 找出最小交换次数，贪心的方案是：最近的先交换 找到最近的在可以用数组数组和set实现 具体细节见代码
#include<bits/stdc++.h> #define debug1(a) cout<<#a<<'='<< a << endl; #define debug2(a,b) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<endl; #define debug3(a,b,c) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<endl; #define debug4(a,b,c,d) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<" "<<#d<<" = "<<d<<endl; #define debug5(a,b,c,d,e) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<" "<<#d<<" = "<<d<<" "<<#e<<" = "<<e<<endl; #define debug0(x) cout << "debug0: " << x << endl #define fr(t, i, n)for (long long i = t; i < n; i++) #define YES cout<<"Yes"<<endl #define NO cout<<"No"<<endl #define fi first #define se second #define int long long using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII; typedef pair<LL,LL> PLL; //#pragma GCC optimize(3,"Ofast","inline") //#pragma GCC optimize(2) const int N = 2e5+10; int aa[N]; int lowbit(int x) // 返回末尾的1 {return x & -x;} void add(int x,int w){ for(int i = x;i < N;i += lowbit(i)){ aa[i] += w; } } int query(int u){ int res = 0; for(int i = u;i > 0;i -= lowbit(i)){ res += aa[i]; } return res; } int a[N],b[N]; multiset<int> A,B; void solve() { int n;cin >> n; for(int i = 1; i <= n; i++)cin >> a[i],A.insert(a[i] + i); for(int i = 1; i <= n; i++)cin >> b[i],B.insert(b[i] + i); if(A != B) { cout << -1 << endl; return ; } set<PII> s; int ans = 0; for(int i = 1; i <= n; i++)s.insert(PII{a[i] + i, i}); for(int i = 1; i <= n; i++) { set<PII>::iterator it = s.lower_bound(PII{b[i]+i,0}); int t = query((*it).second) + (*it).second; add(1,1); assert((*it).second>0); add((*it).second,-1);//这里相对位置不用加1，因为这个是相对于a数组原始位置而言的 ans += t - i; s.erase(it); } cout << ans << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T = 1;//cin >> T; while(T--){ solve(); } return 0; }
