计蒜客三值排序（贪心）

悠悠 2024-02-17 22:03 28阅读 0赞

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

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

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

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

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

##### 样例输入 #####

9
    2
    2
    1
    3
    3
    3
    2
    3
    1

##### 样例输出 #####

4

分析：贪心思想：

将序列排序后，有值为1、2、3共有三个值段；另找三个变量x,y,z；

x:在值段1中不是1的个数；

y:在值段2中值为3的个数；

z:在值段3中值为2的个数；

最小交换次数, x+max(y,z);

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=1000+10;
    int a[maxn];
    int b[maxn];
    
    int main(){
        int n;
    	while(scanf("%d",&n)==1){
    		for(int i=0;i<n;i++)
    		{
    			scanf("%d",&a[i]);
    			b[i]=a[i];
    		}
    		
    		sort(a,a+n);
    		int x=0,y=0,z=0;
            for(int i=0;i<n;i++){
            	if(a[i]==1&&b[i]!=1)x++;
            	else if(a[i]==2&&b[i]==3)y++;
            	else if(a[i]==3&&b[i]==2)z++;
    		}
    		
    		int cnt = x + max(y,z);
    		printf("%d\n",cnt);
    	}	
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，28人围观）

还没有评论，来说两句吧...

相关阅读

相关计蒜客守望者的逃离（贪心）

恶魔猎手尤迫安野心勃勃。他背叛了暗夜精灵，率深藏在海底的那加企图叛变：守望者在与尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座

灰太狼/ 2024年02月17日 22:36/ 0 赞/ 5 阅读

相关计蒜客跳跃游戏（dfs）

给定一个非负整数数组，假定你的初始位置为数组第一个下标。数组中的每个元素代表你在那个位置能够跳跃的最大长度。请确认你是否能够跳跃到数组的最后一个下标。例如：A=\[

女爷i/ 2024年02月17日 22:03/ 0 赞/ 35 阅读

相关计蒜客三值排序（贪心）

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

悠悠/ 2024年02月17日 22:03/ 0 赞/ 29 阅读

相关计蒜客 T1200 Minecraft

题目链接：[https://nanti.jisuanke.com/t/T1200][https_nanti.jisuanke.com_t_T1200] 解题思路：因为立方体的

ゝ一世哀愁。/ 2023年07月09日 05:24/ 0 赞/ 18 阅读

相关【算法积累】计蒜客迷宫三问 (DFS & BFS)

计蒜客T1595 - 迷宫（一） [题目链接][Link 1] 一天蒜头君掉进了一个迷宫里面，蒜头君想逃出去，可怜的蒜头君连迷宫是否有能逃出去的路都不知道。看在

心已赠人/ 2022年09月04日 00:52/ 0 赞/ 289 阅读

相关计蒜客---三值排序

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

墨蓝/ 2022年06月14日 10:23/ 0 赞/ 190 阅读

相关计蒜客奇异家庭

[题目传送门][Link 1] dp\[i\]\[j\] – i 个节点不超过 j 层的方案数有dp\[i\]\[j\]+=dp\[t\]\[j-1\]\dp\[i-t

末蓝、/ 2022年05月14日 00:26/ 0 赞/ 204 阅读

相关计蒜客踏青 dfs

题目： https://www.jisuanke.com/course/2291/182234 思路：紫书P163联通块问题。 1.遍历所有块，找到草地，判断合法性，

系统管理员/ 2022年01月06日 11:47/ 0 赞/ 248 阅读

相关【计蒜客】走迷宫

总而言之，关于迷宫好像大部分都是搜索题.... 先看一下题：（数据范围好小啊给一个n行m列的2维的迷宫，`'S'`表示迷宫的起点，`'T'`表示迷宫的

╰+哭是因爲堅強的太久メ/ 2021年12月21日 20:55/ 0 赞/ 293 阅读

相关计蒜客 - 汉诺塔

问题: ![1516087-20190501155629805-481143157.png][] 思路: 汉诺塔问题非常经典，不懂推荐去看B站正月点灯笼老师的对于汉诺塔的

悠悠/ 2021年12月03日 15:55/ 0 赞/ 313 阅读