题意
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;
}