一個很眼熟的貪心 首先一個序列對他編好號后，末狀態編號的逆序對數就是交換相鄰2個達到這個狀態需要的最少次數 將A序列1~n編號，再對B序列按順序每個字母賦這個字母有的所有編號里最小的這樣能使得逆序對數最少，然后求B的逆序對數
code：
#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long long#define lowbit(x) x&(-x)using namespace std;const int maxn = 1100000;queue<int>Q[26];int n;int s[maxn];struct node{ int x,i; node(){} node(int _x,int _i){x=_x;i=_i;}}a[maxn];bool cmp(node x,node y){return x.x<y.x;}void add(int x){for(;x<=n;x+=lowbit(x))s[x]++;}int query(int x){ int r=0; for(;x;x-=lowbit(x)) r+=s[x]; return r;}int main(){ char str; scanf("%d",&n); getchar(); for(int i=1;i<=n;i++) { scanf("%c",&str); Q[str-'A'].push(i); }getchar(); for(int i=1;i<=n;i++) { scanf("%c",&str); int j=str-'A'; int x=Q[j].front(); Q[j].pop(); a[i]=node(x,i); } sort(a+1,a+n+1,cmp); ll re=0; for(int i=n;i>=1;i--) { re+=(ll)query(a[i].i); add(a[i].i); }新聞熱點
疑難解答
