题解：洛谷 P1459 [USACO2.1] 三值的排序 Sorting a Three-Valued Sequence

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1459 [USACO2.1] 三值的排序 Sorting a Three-Valued Sequence - 洛谷【题目描述】排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种 1,2,3。我们用交换的方法把他排成升序的。写一个程序计算出给定的一个 1,2,3 组成的数字序列排成升序所需的最少交换次数【输入】第一行一个正整数n表示奖牌个数。接下来n行每行一个 [1,3] 内的整数表示奖牌。【输出】输出一行一个整数表示排成升序所需的最少交换次数。【输入样例】9 2 2 1 3 3 3 2 3 1【输出样例】4【核心思想】问题分析给定一个由1 , 2 , 3 1, 2, 31,2,3组成的序列要求通过交换操作将其排成升序所有1 11在前2 22在中3 33在后求最少交换次数。排序后1 11的区间为[ 1 , n u m [ 1 ] ] [1, num[1]][1,num[1]]2 22的区间为[ n u m [ 1 ] 1 , n u m [ 1 ] n u m [ 2 ] ] [num[1]1, num[1]num[2]][num[1]1,num[1]num[2]]3 33的区间为[ n u m [ 1 ] n u m [ 2 ] 1 , n ] [num[1]num[2]1, n][num[1]num[2]1,n]。算法选择贪心交换策略优先处理直接互换一次交换解决两个错位再处理三角互换两次交换解决三个错位错位分类将错位的元素按所在区间和目标区间分类统计六种错位类型关键步骤统计数量遍历序列统计n u m [ 1 ] , n u m [ 2 ] , n u m [ 3 ] num[1], num[2], num[3]num[1],num[2],num[3]各数字出现次数确定排序后三个区间的边界第一轮直接互换一次交换修复两个位置[ 1 , 2 ] [1,2][1,2]互换在1 11的区间内找2 22在2 22的区间内找1 11配对交换[ 1 , 3 ] [1,3][1,3]互换在1 11的区间内找3 33在3 33的区间内找1 11配对交换[ 2 , 3 ] [2,3][2,3]互换在2 22的区间内找3 33在3 33的区间内找2 22配对交换第二轮三角互换一次交换修复一个位置剩余错位形成三角循环在1 11的区间内找非1 11的元素与后面区间中的1 11交换在2 22的区间内找非2 22的元素与后面区间中的2 22交换输出结果总交换次数a n s ansans时间/空间复杂度时间复杂度O ( n 2 ) O(n^2)O(n2)最坏情况下需要双重循环查找配对元素空间复杂度O ( n ) O(n)O(n)存储序列数组贪心交换的核心思想直接互换优先a [ i ] 2 , a [ j ] 1 a[i]2, a[j]1a[i]2,a[j]1且i ii在1 11区间、j jj在2 22区间时一次交换同时修复两个位置成本最低三角循环处理直接互换后剩余的错位元素形成三角循环如1 11区间有2 222 22区间有3 333 33区间有1 11需要两次交换修复三个位置区间边界固定排序后各数字的位置区间由数量唯一确定无需实际排序即可知道每个元素的目标位置贪心最优性优先执行直接互换不会破坏后续更优解且每次直接互换减少两个错位是局部最优选择适用于有限取值排序、最小交换次数、错位修复类问题【解题思路】【算法标签】#普及- #贪心【代码详解】#includebits/stdc.husingnamespacestd;intn,num[5],a[1005],ans0;intmain(){cinn;// 输入nfor(inti1;in;i){// 依次输入n个值cina[i];num[a[i]];// 同时记录每个数的数量}for(inti1;inum[1];i){// 在排序后1的范围和2的范围内for(intjnum[1]1;jnum[1]num[2];j){if(a[i]2a[j]1){// 查找[2,1]和[1,2]的情况swap(a[i],a[j]);// 进行对调ans;break;}}}for(inti1;inum[1];i){// 在排序后1的范围和3的范围内for(intjnum[1]num[2]1;jn;j){if(a[i]3a[j]1){// 查找[3,1]和[1,3]的情况swap(a[i],a[j]);// 进行对调ans;break;}}}for(intinum[1];inum[1]num[2];i){// 在排序后2的范围和3的范围内for(intjnum[1]num[2]1;jn;j){if(a[i]3a[j]2){// 查找[3,2]和[2,3]的情况swap(a[i],a[j]);// 进行对调ans;break;}}}for(inti1;inum[1];i){// 在排序后1的范围和2、3范围内for(intjnum[1]1;jn;j){if(a[i]!1a[j]1){// 查找不等于1和等于1的swap(a[i],a[j]);// 进行对调ans;break;}}}for(intinum[1]1;inum[1]num[2];i){// 在排序后2的范围和3的范围内for(intjnum[1]num[2]1;jn;j){if(a[i]!2a[j]2){// 查找不等于2和等于2的swap(a[i],a[j]);// 进行对调ans;break;}}}coutansendl;// 输出调换次数return0;}【运行结果】9 2 2 1 3 3 3 2 3 1 4