题解：洛谷 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

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

相关推荐

VLC Android播放器使用指南：7个真实场景带你从新手用到顺手

从创客视角解析传感器投送系统：机械设计与Arduino控制实战

大模型API防蒸馏机制解析与合规高效应用架构实践

更多资讯

PS5折腾指南：系统配置、存储扩展、远程游玩与散热维护

边缘实时分析系统架构设计与实践：边缘计算下的轻量级数据处理与智能化决策

Python+Vue前后端分离学生选课管理系统开发实战

Vivo手机数据备份与恢复全指南：换机迁移防丢数据实操

数据复制深度拆解：从HDFS块复制到CDC同步的机制、实践与容灾设计

AI芯片软硬件协同设计实战：从GPU瓶颈到专用架构的权衡

今日更新

Susi AI API实战指南：susi_alexa_skill如何用Node.js调用chat.json获取智能回答

换新电脑了？KeyStats 恢复码数据找回完全指南，端到端加密统计一键重建

重建二叉树：由前序与中序遍历序列还原二叉树的原理与 Java 实现（YCBlogs 剑指 Offer 精讲）

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？