Codeforces Round #324 (Div. 2) E. Anton and Ira 贪心

题目

题意：

　　给出两个有相同元素的数组a，数组b，使 a[i]和 a[j] 进行交换，得到数组 b ，每次交换的代价为abs( i - j )。

　　　要求输出最小的总代价，交换的步数，以及每次交换的两个位置。

思路：

　　如果数组 a : 5 2 1 4 6 3

　　　　　数组 b: 1 2 3 4 5 6

　　　只需对数组b的每项b[ i ]，尽量使数组a中值为b[ i ]的位置和别的a[ j ]所在的位置交换，使得最终a[i]==b[i] 。

　　 b[1]=1，在a中找到 a[3]=1，位置为3 ，记做k=3，此时a中 5占据了1的位置，尝试着交换看看。 5 在b中的位置是第5，5>=k，说明如果a中 a[1]和a[3]交换，即值 5 和1交换，就得到 1 2 5 4 6 3，这样1就归位了（a[i]==b[i]），而且5此时的位置变成3，离5更近了。这次交换，使得1归位，使5离目的地更近了，说明在交换过程中代价是最小的，没有交换过头的现象，这样的交换是最贪心的。

　　　 b[1]处理完了，再处理b[2]，按上面的思路使a[2]==b[2]，以此类推。应该是O(n^2)的复杂度。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include <cctype>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cmath>
 7 #include<string>
 8 #include<cmath>
 9 #include<set>
10 #include<vector>
11 #include<stack>
12 #include<queue>
13 #include<map>
14 using namespace std;
15 #define ll long long
16 #define mem(a,x) memset(a,x,sizeof(a))
17 #define se second
18 #define fi first
19 const ll mod=1e9+7;
20 const int INF= 0x3f3f3f3f;
21 const int N=2e6+5;
22 
23 int n,cnt,ans;
24 int a[N],b[N];
25 int p[N];
26 int ans1[N],ans2[N];
27 
28 
29 int main()
30 {
31     
32         scanf("%d",&n);
33         for(int i=1;i<=n;i++)    scanf("%d",&a[i]);
34         for(int i=1;i<=n;i++)    scanf("%d",&b[i]),p[b[i]]=i;
35         
36         cnt=0;
37         ans=0;
38         for(int i=1;i<=n;i++)
39         {
40             int k=i;
41             
42             if(b[i]!=a[i])  //找到b[i]在a中的位置k 
43             {
44                 for(int j=i+1;j<=n;j++)
45                 {
46                     if(b[i]==a[j]){
47                         k=j; break;  
48                     }
49                 }
50             }
51             
52             while(k!=i) //意味着还不归位，a[i]!=b[i] 
53             {
54                 for(int j=i;j<k;j++)
55                 {
56                     if(p[a[j]]>=k) //a[j]的位置在k的后面
57                     {
58                         ans+=abs(k-j);
59                         ans1[cnt]=j;
60                         ans2[cnt]=k;
61                         cnt++;
62                         
63                         swap(a[j],a[k]);
64                         swap(j,k); //这一步 保证k随着交换移前，也保证此for的终结 
65                         
66                         
67                     } 
68                 }
69             }
70             
71         }
72         
73         cout<<ans<<endl;
74         cout<<cnt<<endl;
75         for(int i=0;i<cnt;i++)
76             cout<<ans1[i]<<' '<<ans2[i]<<endl;
77         
78     
79 }

View Code

　　如果n太大，想直接得到步数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int a[200005],b[200005];
 5 int conv[200005];
 6 int main()
 7 {
 8     int zu;
 9     scanf("%d",&zu);
10     while(zu--)
11     {
12         int n;
13         scanf("%d",&n);
14         for(int i=1;i<=n;i++) scanf("%d",&a[i]),conv[a[i]]=i;
15         for(int i=1;i<=n;i++) scanf("%d",&b[i]);
16         ll ans=0;
17         for(int i=1;i<=n;i++) ans+=abs(i-conv[b[i]]);
18         printf("%lld
",ans/2);
19     }
20 }

View Code