51nod 1574 || Codeforces 584 E. Anton and Ira 思维+构造+贪心

传送门：E. Anton and Ira

题意：给定两个1-n的全排列p和s，假设交换pi和pj的代价是abs(i-j)，问怎样将p交换成s才能使代价最小。

思路：先将s映射成1-n的顺序排列，再将p根据同一映射函数映射成新的序列，得到新问题与原问题等价（并不会证明，但是dalao们都这么说）

现在我们要做的就是将pi移到i位置上，我们可以先从最小的pi开始移动，这样当我们移动任何一个pi时，假设pi当前位置为x，我们都能保证pi<=x,如果pi==x,那么移动结束，否则我们可以一直将pi向左交换，使得其越来月接近目标位置，在这个过程中，pi是不会产生更多代价的，但是和pi交换的元素有可能产生更多代价，因此我们每次必定要挑选pj>=x的pj去和pi交换，这样才能保证总代价不变大，可以证明[i,x-1]区间内一定存在pj>=x.（可以用抽屉原理证明）

代码：

#include<bits/stdc++.h>using namespace std;int p[],s[],f[];int n;typedef pair<int,int> P;vector<P>ans;int main(){cin >> n;for(int i=1;i<=n;i++) cin >> p[i];for(int i=1;i<=n;i++) cin >> s[i];for(int i=1;i<=n;i++){f[s[i]] = i;// f为一一映射的映射函数 }for(int i=1;i<=n;i++){p[i] = f[p[i]]; // 将p序列也对应一一映射过去 }int sum = 0;while(1){int pos = 0;for(int i=1;i<=n;i++){if(p[i] != i && (!pos || p[pos] > p[i]))pos = i;}if(!pos) break;for(int i=pos;i>=p[pos];i--){if(p[i] >= pos){ans.push_back(P(i, pos));swap(p[i], p[pos]);sum += abs(i - pos);pos = i;}}} printf("%d\n%d\n",sum,ans.size());for(int i=0;i<ans.size();i++)printf("%d %d\n",ans[i].first, ans[i].second); }

传送门：51nod 1574

题意：上面题的翻版，思路简化，数据量变大。

思路：由于我们不需要输出交换的的过程了，因此我们的交换就可以‘一步到位’了，但是第一步的映射过程还是需要的，然后对于每个数直接计算其当前位置和其目标位置的差值加到答案里就行了，注意由于是交换，因此答案要除以2.

代码：

#include<stdio.h>#include<bits/stdc++.h>using namespace std;int p[200020],s[200020],f[200020];int n;int main(){cin >> n;for(int i=1;i<=n;i++) scanf("%d", p + i);for(int i=1;i<=n;i++) scanf("%d", s + i);for(int i=1;i<=n;i++){f[s[i]] = i;// f为一一映射的映射函数}for(int i=1;i<=n;i++){p[i] = f[p[i]]; // 将p序列也对应一一映射过去}long long sum = 0;for(int i = 1; i <= n; i++){sum += abs(i - p[i]);}printf("%lld\n",sum / 2);}