Codeforces 489A SwapSort 题解

xiaoxiao2021-02-27  212

题意

n个数,每次允许交换任意两个数,使得这个数列最后成为不降序列,问最少需要交换多少次,每一次怎么做

思路

从前往后扫,每一次把后边的最小的数换到前边来,如果最小数就是本身就不用东

代码

#include <cstdio> #include <vector> using namespace std; int a[3001]; vector<pair<int,int> > ans; int main() { int n,minn,minj; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<n;i++) { minn=1000000001; minj=-1; for(int j=i;j<n;j++) if(a[j]<minn) { minn=a[j]; minj=j; } if(minj!=i) { ans.push_back(make_pair(i,minj)); swap(a[i],a[minj]); } } printf("%d\n",ans.size()); for(int i=0;i<ans.size();i++) printf("%d %d\n",ans[i].first,ans[i].second); return 0; }
转载请注明原文地址: https://www.6miu.com/read-12890.html

最新回复(0)