【題目來源】
http://oj.ecustacm.cn/problem.php?id=1812
http://oj.ecustacm.cn/viewnews.php?id=1023
【題目描述】
給定一個(gè)長(zhǎng)度為 n 的排列 a，需要將這個(gè)排列變成 b。
每次可以選擇一個(gè)數(shù)字往左移若干個(gè)位置。
請(qǐng)求出最小需要移動(dòng)的元素個(gè)數(shù)。
【輸入格式】
第一行為正整數(shù) n，1≤n≤100000。
第二行為 n 個(gè)整數(shù)，表示排列 a。
第三行為 n 個(gè)整數(shù)，表示排列 b。
【輸出格式】
輸出一個(gè)數(shù)字表示答案，即最小需要移動(dòng)的元素個(gè)數(shù)。
【輸入樣例】
5
5 1 3 2 4
4 5 2 1 3
【輸出樣例】
2
【算法分析】
** 將原序列 a 重排為序列 b，則原序列 a 中各元素在序列 b 中的位置?p[] 可通過以下代碼獲得：
tp[b[i]]=i, p[i]=tp[a[i]]
**?分析位置序列 p[] 中每個(gè)數(shù)，如果當(dāng)前的數(shù)比左邊的數(shù)小就不斷左移，否則不用移動(dòng)。這是貪心算法的思路。
例如，針對(duì)樣例中給出的原始序列 a[]=[5 1 3 2 4] 中的各元素，利用“tp[b[i]]=i, p[i]=tp[a[i]]”，可得出它們?cè)谥嘏判蛄?b[]=[4 5 2 1 3] 中的位置序列為 p[]=[2 4 5 3 1]。顯然，通過觀察位序的相對(duì)位置，可知需要移動(dòng)兩個(gè)數(shù)字。
【算法代碼】文章來源：http://www.zghlxwxcb.cn/news/detail-660776.html
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N];
int p[N]; //p[x]:subscript of number x in the b array
int tp[N];
int main() {
int n;
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++) {
cin>>b[i];
tp[b[i]]=i;
}
for(int i=1; i<=n; i++) p[i]=tp[a[i]];
int ans=0;
int t=0;
for(int i=1; i<=n; i++) {
if(t>p[i]) ans++;
t=max(t,p[i]);
}
cout<<ans<<endl;
return 0;
}
/*
in:
5
5 1 3 2 4
4 5 2 1 3
out:
2
*/
【參考文獻(xiàn)】
https://blog.csdn.net/weixin_43914593/article/details/131741061
?文章來源地址http://www.zghlxwxcb.cn/news/detail-660776.html
到了這里，關(guān)于羅勇軍 → 《算法競(jìng)賽·快沖300題》每日一題：“排列變換” ← 貪心算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
