Codeforces 1375 E. Inversion SwapSort —— 想法，贪心

本文主要是介绍Codeforces 1375 E. Inversion SwapSort —— 想法，贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

现在有一个长度为n的数组，让你按照一个顺序去交换所有一开始的数组的逆序对的位置，从而使得最终的数组非递减。

题解：

那么就是从前往后去做，对于当前位置，找到所有一开始数组中的它与它之后的逆序对的位置，然后按照数值从大到小去交换，这样的话，既能保证最终放在这个位置的值是当前最小的，又能不破坏后面的值的大小情况。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
#define pa pair<int,int>
int a[N];
vector<pa>ans,b;
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++)if(a[j]<a[i])b.push_back({a[j],j});if(!b.size())continue;sort(b.begin(),b.end(),greater<pa>());for(auto j:b)ans.push_back({i,j.second});b.clear();}printf("%d\n",ans.size());for(auto i:ans)printf("%d %d\n",i.first,i.second);return 0;
}

这篇关于Codeforces 1375 E. Inversion SwapSort —— 想法，贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---