三值排序
发布日期:2022-02-08 04:20:45 浏览次数:3 分类:技术文章

本文共 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 1000
int 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:java 自定义比较器
下一篇:纪念品分组

发表评论

最新留言

很好
[***.229.124.182]2024年03月01日 05时37分17秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

airpodspro没有弹窗_使用AirPods Pro一天的主观感受 2019-04-21
创建物化视图commit_视图及范式 2019-04-21
函数传参字典_Python新手上车17:函数传递任意多个参数 2019-04-21
去掉数组最后一个元素_【一天一大 lee】在排序数组中查找元素的第一个和最后一个位置 (难度:中等) Day20201201... 2019-04-21
秦九韶算法递推公式_算法讲解之复杂度分析 2019-04-21
添加绝对路径_网站中如何添加绝对路径 2019-04-21
python房价数据分析波士顿代码数据_python数据分析-波士顿房价预测-Go语言中文社区... 2019-04-21
redis线程阻塞原因排插_Redis阻塞原因详解 2019-04-21
labview自动保存报表_基于LabVIEW的Excel报表的自动生成功能 2019-04-21
geotool 导出shp_Java 读取shape文件 2019-04-21
mysql 关联更新_MySQL UPDATE多表关联更新 2019-04-21
mysql call_mysql的call用法 call调用函数的例子 2019-04-21
python参数验证_参数验证,Python中的最佳实践 2019-04-21
python画多层网络_在pymn中修改多层网络图 2019-04-21
java net 安卓_android -------- java.net.UnknownServiceException 2019-04-21
java 密钥 aes 解密_Java中AES加密解密以及签名校验 2019-04-21
java树转化成图_Java 转换一组数据为树型数据 2019-04-21
java 底层ppt_Java 如何设置 PPT 中的形状排列方式 具体内容 2019-04-21
mysql更新第5条记录_MYSQL中添加、更新、删除数据 2019-04-21
mysql service5.7_Mysql5.7服务下载安装 2019-04-21