Codeforces584E【贪心】

挣扎了好久！
逆序数好6啊！
直接把s数组映射成1,2,3,4,5,6
然后从1开始强势贪，如果小于其位置的数就往前找一个值大于等于该位置的位置，然后这一步肯定是必然的（互优的），然后就写完了。复杂度n^2，然后51nod1574显得更加强势，当然少了输出路径也就变成了一些每个数都在走必然最优的步，答案也就是他们要走的区间和/2。
= =mmp挫代码还搞了个p代表位置（想挫了也就写挫了，不过收益蛮大

#include <bits/stdc++.h>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long LL;
const int Maxn = 2e3 + 10;
//map real number
int mp[Maxn], a[Maxn], num, p[Maxn], pos;
int ans1[Maxn*1000], ans2[Maxn*1000];
int n, x, j;
int main(){
LL res = 0;
scanf("%d", &n);
for(int i=1;i<=n;i++)
scanf("%d", &a[i]);
for(int i=1;i<=n;i++){
scanf("%d", &x);
mp[x] = i;
}
for(int i=1;i<=n;i++){
a[i] = mp[a[i]];
p[a[i]] = i;
}
num = 0;
for(int i=1;i<=n;i++){
pos = p[i];
while(1){
if(pos == i) break;
j = pos - 1;
while(a[j] < pos)
j--;
res = res + abs(pos - j);
ans1[num] = pos;ans2[num] = j;num++;
swap(p[a[pos]], p[a[j]]);
swap(a[pos], a[j]);
pos = j;
}
}
printf("%I64dn", res);
printf("%dn", num);
for(int i=0;i<num;i++) printf("%d %dn",ans1[i], ans2[i]);
return 0;
}

最后

以上就是纯真小海豚为你收集整理的Codeforces584E【贪心】的全部内容，希望文章能够帮你解决Codeforces584E【贪心】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。