UVa 612 DNA Sorting
题目描述序列中的“无序度”可以用逆序对的数量来衡量。例如字母序列DAABEC中D大于其右侧的四个字母E大于其右侧的一个字母因此逆序数为555。序列AACEDGG仅有一个逆序对E和D几乎有序而ZWQM有666个逆序对是完全逆序的。你需要对一组DNA\texttt{DNA}DNA字符串仅包含A、C、G、T四种字符进行排序但不是按字母顺序而是按“有序程度”从“最有序”到“最无序”排列。所有字符串长度相同。若两个字符串逆序数相同则保持它们在输入中的相对顺序。输入格式第一行为一个整数MMM表示数据集的个数。接下来每个数据集的第一行包含两个整数nnn0n≤500 n \le 500n≤50表示字符串长度mmm0m≤1000 m \le 1000m≤100表示字符串个数。随后mmm行每行一个长度为nnn的字符串仅含A、C、G、T。不同数据集之间可能存在空行但cin可以忽略空白字符。输出格式对于每个数据集输出mmm行每行一个字符串按逆序数从小到大排列。若逆序数相同保持输入顺序。不同数据集的输出之间用一个空行分隔。样例输入1 10 6 AACATGAAGG TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA ATCGATGCAT输出CCCGGGGGGA AACATGAAGG GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA题目分析本题的核心是计算每个字符串的逆序数并按逆序数升序排序。逆序数的定义在一个序列中如果一对字符iji jij但sisjs_i s_jsi​sj​按字符ASCII\texttt{ASCII}ASCII码大小比较则构成一个逆序对。由于字符串长度n≤50n \le 50n≤50直接使用两层循环枚举所有字符对即可在O(n2)O(n^2)O(n2)时间内算出逆序数总复杂度O(m⋅n2)O(m \cdot n^2)O(m⋅n2)完全可行。排序时需要保持逆序数相同元素的原始顺序因此应使用稳定排序算法如stable_sort。这与样例中逆序数相同的字符串保持原输入顺序的要求一致。解题思路读入MMM表示数据集个数。对于每个数据集读入nnn和mmm。循环mmm次读入每个字符串。对每个字符串通过两层循环统计逆序数对于iii从000到n−1n-1n−1jjj从i1i1i1到n−1n-1n−1若line[j] line[i]则逆序数加111。将字符串和其逆序数存入结构体数组。使用stable_sort按逆序数升序排序。按排序后的顺序输出字符串。若非最后一个数据集输出一个空行即相邻数据集间空行。复杂度分析每个字符串计算逆序数O(n2)O(n^2)O(n2)n≤50n \le 50n≤50常数很小。排序O(mlog⁡m)O(m \log m)O(mlogm)m≤100m \le 100m≤100。总时间复杂度O(M⋅m⋅n2)O(M \cdot m \cdot n^2)O(M⋅m⋅n2)MMM未知但通常较小完全可接受。空间复杂度O(m)O(m)O(m)用于存储字符串和逆序数。代码实现// DNA Sorting// UVa ID: 612// Verdict: Accepted// Submission Date: 2016-08-23// UVa Run Time: 0.030s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structitem{string dna;intinversion;booloperator(constitemanother)const{returninversionanother.inversion;}};intgetInversion(stringline){intinversion0;for(inti0;iline.length();i)for(intji1;jline.length();j)if(line[j]line[i])inversion;returninversion;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0,n,m;cincases;vectoritemdnas;for(intc1;ccases;c){dnas.clear();if(c1)cout\n;cinnm;cin.ignore(1024,\n);string line;for(inti0;im;i){getline(cin,line);dnas.push_back((item){line,getInversion(line)});}stable_sort(dnas.begin(),dnas.end());for(autodata:dnas)coutdata.dna\n;}return0;}总结本题是一个典型的排序应用题核心在于正确计算逆序数并利用稳定排序保证相同逆序数的字符串保持原顺序。由于数据规模极小直接暴力计算即可。该题也提醒我们在排序时若需保持相等元素的原始顺序应当使用稳定排序算法如stable_sort而不是普通sort。此解法简洁高效适合作为入门级排序与模拟练习题。

相关新闻

所谓的“休息羞耻”:只是不把自己当回事罢了

所谓的“休息羞耻”:只是不把自己当回事罢了

离职就该有负罪感?别被“上班至上”PUA了 目录 离职就该有负罪感?别被“上班至上”PUA了 最近刷到一段话,看完心里一下子松了。 “如果你离职了,就好好休息一段时间,千万不要有什么负罪感。休息一段时间没有错,躺着发呆也没有罪。这世界只有上班猝死的,没有不上班饿死的…

2026/6/29 7:08:06阅读更多 →
Web安全基石:深入理解XSS攻击原理、类型与纵深防御策略

Web安全基石:深入理解XSS攻击原理、类型与纵深防御策略

1. 项目概述:从“弹窗”到“数据窃取”,重新认识XSS如果你在浏览某个论坛时,突然页面上弹出一个莫名其妙的“恭喜中奖”的弹窗,或者你的个人主页签名被篡改成了一段奇怪的文字,那么你很可能已经遭遇了一次典型的XSS攻击…

2026/6/29 7:08:06阅读更多 →
openEuler网络优化技术:Gazelle高性能网络框架使用详解

openEuler网络优化技术:Gazelle高性能网络框架使用详解

openEuler网络优化技术:Gazelle高性能网络框架使用详解 【免费下载链接】docs-centralized To build and enrich documentation for openEuler project. 项目地址: https://gitcode.com/openeuler/docs-centralized 前往项目官网免费下载:https:/…

2026/6/29 7:08:06阅读更多 →
CP-17 SOME/IP协议栈深度解析 - 面向服务的车载中间件从协议原理到AUTOSAR工程实战

CP-17 SOME/IP协议栈深度解析 - 面向服务的车载中间件从协议原理到AUTOSAR工程实战

CP-17 SOME/IP协议栈深度解析 —— 面向服务的车载中间件从协议原理到AUTOSAR工程实战 系列导航 文章编号文章标题CP-01AUTOSAR CP快速入门指南CP-02BSW层综述与RTE的作用......CP-16车载以太网TCP/IP协议栈全栈深度解析CP-17SOME/IP协议栈深度解析 目录 引言:从…

2026/6/29 8:18:13阅读更多 →
AP-14 DDSI-RTPS协议深度解析 - 发现机制、可靠传输与线协议报文结构的硬核拆解

AP-14 DDSI-RTPS协议深度解析 - 发现机制、可靠传输与线协议报文结构的硬核拆解

AP-14 DDSI-RTPS协议深度解析 - 发现机制、可靠传输与线协议报文结构的硬核拆解 📚 AUTOSAR AP实战指南系列导航 AP-01~AP-12:已完成(基础架构、COM、E2E、安全通信等)AP-13:DDS核心架构与QoS策略体系(已发…

2026/6/29 8:18:13阅读更多 →
C链接库,联动 Rust、Golang、Python

C链接库,联动 Rust、Golang、Python

基础概念铺垫 1. 链接库是什么? 写代码时很多通用功能(加密、网络、数学计算)不用每次重写,把一堆函数、变量、类打包成独立二进制文件,这个文件就是链接库。 程序编译时分两步: 编译:源代码 →…

2026/6/29 8:18:13阅读更多 →
DLSS Swapper完整指南:简单三步实现游戏性能智能优化

DLSS Swapper完整指南:简单三步实现游戏性能智能优化

DLSS Swapper完整指南:简单三步实现游戏性能智能优化 【免费下载链接】dlss-swapper 项目地址: https://gitcode.com/GitHub_Trending/dl/dlss-swapper 你是否曾为游戏帧率不稳定而苦恼?是否想提升游戏性能却不知从何下手?DLSS Swapp…

2026/6/29 8:18:13阅读更多 →
终极精简指南:如何使用PowerShell脚本将Windows 11系统瘦身50%

终极精简指南:如何使用PowerShell脚本将Windows 11系统瘦身50%

终极精简指南:如何使用PowerShell脚本将Windows 11系统瘦身50% 【免费下载链接】tiny11builder Scripts to build a trimmed-down Windows 11 image. 项目地址: https://gitcode.com/GitHub_Trending/ti/tiny11builder 你是否厌倦了Windows 11那臃肿的系统体…

2026/6/29 8:18:13阅读更多 →
3步解决容器镜像下载难题:DaoCloud镜像加速实战指南

3步解决容器镜像下载难题:DaoCloud镜像加速实战指南

3步解决容器镜像下载难题:DaoCloud镜像加速实战指南 【免费下载链接】public-image-mirror 很多镜像都在国外。比如 gcr 。国内下载很慢,需要加速。致力于提供连接全世界的稳定可靠安全的容器镜像服务。 项目地址: https://gitcode.com/GitHub_Trendin…

2026/6/29 8:13:12阅读更多 →
AI Coding 六个月真实ROI账本:产品经理的血泪教训,研发的冷静忠告

AI Coding 六个月真实ROI账本:产品经理的血泪教训,研发的冷静忠告

6个月前的2025年12月,Boris Cherny 公开宣布自己卸载了 IDE。一时间,Vibe Coding 成了全行业最热的话题。6个月后,当我们回过头来拉一份真实账本,发现事情远没有"一句话生成一个App"那么浪漫。本文从产品经理和研发两个…

2026/6/29 3:27:55阅读更多 →
审计来了,数据权限全开——审计走了,怎么确保权限全部关掉?

审计来了,数据权限全开——审计走了,怎么确保权限全部关掉?

引言:审计结束三个月了,审计员的权限还没关某城商行每年按照监管要求开展至少一次数据安全审计。审计期间,内审部门需要抽样检查各类业务数据——交易流水、客户信息、员工操作日志、权限配置记录。这些数据分布在不同系统中,审计…

2026/6/29 2:19:08阅读更多 →
如何在3秒内从普通图片生成专业级法线贴图:DeepBump的终极指南

如何在3秒内从普通图片生成专业级法线贴图:DeepBump的终极指南

如何在3秒内从普通图片生成专业级法线贴图:DeepBump的终极指南 【免费下载链接】DeepBump Normal & height maps generation from single pictures 项目地址: https://gitcode.com/gh_mirrors/de/DeepBump 还在为3D建模中的纹理制作而烦恼吗?…

2026/6/29 0:01:47阅读更多 →
OCAuxiliaryTools:终极OpenCore配置工具,让黑苹果安装从未如此简单!

OCAuxiliaryTools:终极OpenCore配置工具,让黑苹果安装从未如此简单!

OCAuxiliaryTools:终极OpenCore配置工具,让黑苹果安装从未如此简单! 【免费下载链接】OCAuxiliaryTools Cross-platform GUI management tools for OpenCore(OCAT) 项目地址: https://gitcode.com/gh_mirrors/oc/OCA…

2026/6/29 0:01:47阅读更多 →
终极Windows 11精简指南:使用tiny11builder快速创建纯净系统镜像

终极Windows 11精简指南:使用tiny11builder快速创建纯净系统镜像

终极Windows 11精简指南:使用tiny11builder快速创建纯净系统镜像 【免费下载链接】tiny11builder Scripts to build a trimmed-down Windows 11 image. 项目地址: https://gitcode.com/GitHub_Trending/ti/tiny11builder 你是否厌倦了Windows 11系统自带的20…

2026/6/29 0:01:47阅读更多 →