本文共 633 字，大约阅读时间需要 2 分钟。

排序是一种很频繁的计算任务。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种1，2和3。我们用交换的方法把他排成升序的。

写一个程序计算出，计算出的一个包括1、2、3三种值的数字序列，排成升序所需的最少交换次数。

输入第1行为类别的数量N（1≤N≤1000）

输入第2行到第N+1行，每行包括一个数字（1或2或3）。

输出包含一行，为排成升序所需的最少交换次数。

#include<bits/stdc++.h>

using namespace std;#define N 1000int main(){ int n,sum1=0,sum2=0,sum3=0; cin>>n; int a[4]={0}; int k[N]; for(int i=0;i<n;i++){ cin>>k[i]; a[k[i]]++; } for(int j=0;j<a[1];j++){ if(k[j]!=1) sum1++; } for(int j=a[1];j<a[1]+a[2];j++){ if(k[j]==3) sum2++; } for(int j=a[1]+a[2];j<n;j++){ if(k[j]==2) sum3++; } //cout<<a[1]<<"---"<<a[2]<<"---"<<a[3]<<"---"<<endl; cout<<sum1+max(sum3,sum2)<<endl; return 0;}

转载地址：https://blog.csdn.net/weixin_38960774/article/details/79368980 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！