
三值排序
发布日期:2022-02-08 04:20:45
浏览次数:1
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2023年08月29日 17时22分32秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【Linux】线程安全问题
2019-03-07
【Linux】死锁
2019-03-07
【Linux】posix版本的信号量
2019-03-07
【Linux】读写锁
2019-03-07
【网易邮箱】换绑安全手机(①之前的手机号注销了怎么办 ②网易人工客服在哪)
2019-03-07
【C++】面向对象的三大特性---继承
2019-03-07
【C++】面向对象的三大特性---多态
2019-03-07
[剑指 Offer 46.] 把数字翻译成字符串
2019-03-07
[剑指 Offer 47.] 礼物的最大价值
2019-03-07
【热题 HOT100】96. 不同的二叉搜索树
2019-03-07
【C++】智能指针详解及原理简单说明
2019-03-07
【力扣】[热题 HOT100] 98.验证二叉搜索树
2019-03-07
【力扣】[热题 HOT] 105.前序与中序遍历序列构造二叉树
2019-03-07
【进程】进程的基本概念理解
2019-03-07
【进程】wait() 函数详细分析
2019-03-07
【进程】进程间通信详解
2019-03-07
【力扣】[热题HOT] 114. 二叉树展开链表
2019-03-07
【数据结构】时间复杂度和空间复杂度详解
2019-03-07
【数据结构】线形顺序结构----顺序表(包含全部代码实现)
2019-03-07
使用清华园镜像快速下载安装Python第三方包(简单快捷)
2019-03-07