题目:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=107&page=show_problem&problem=82
题目的要求是找出字典序中的下一个排列。
从后往前查找,如果一直都是非递减的,那么就是“No Successor”。一旦发现不符合条件的字符(if(str[i]<str[i+1]),那么就把该字符与它后面的所有字符中恰好比它大的字符调换,比方说sample中的abaacb,我们找到第一个不符合非递减条件的字母:中间的那个a,然后将它与b调换,因为在那个a后面是cb,恰好比a大的是b。第三步就是把该字符后面的所有字符按字典序排序,在sample中就是把ca排序成为ac,结束。
讲得不是很清楚,其实就是一个进位的思想,找到了那个不符合条件的字符,而它后面的都是字典序逆序,它后面的字典序中的下一个排列就是要“进位”了,所以就把那个找到的字符与它后面的所有字符中恰好比它大的字符调换,就完成了“进位”,然后还要把找到的字符后面的所有字符按字典序排序。
题目的要求是找出字典序中的下一个排列。
从后往前查找,如果一直都是非递减的,那么就是“No Successor”。一旦发现不符合条件的字符(if(str[i]<str[i+1]),那么就把该字符与它后面的所有字符中恰好比它大的字符调换,比方说sample中的abaacb,我们找到第一个不符合非递减条件的字母:中间的那个a,然后将它与b调换,因为在那个a后面是cb,恰好比a大的是b。第三步就是把该字符后面的所有字符按字典序排序,在sample中就是把ca排序成为ac,结束。
讲得不是很清楚,其实就是一个进位的思想,找到了那个不符合条件的字符,而它后面的都是字典序逆序,它后面的字典序中的下一个排列就是要“进位”了,所以就把那个找到的字符与它后面的所有字符中恰好比它大的字符调换,就完成了“进位”,然后还要把找到的字符后面的所有字符按字典序排序。
#include<stdio.h> #include<stdlib.h> #include<string.h> int cmp(void const *a,void const *b) { return *((char *)a)-*((char *)b); } int main() { char str[100]; for(;;) { int i,len,flag=0; scanf("%s",str); if(str[0]=='#') break; len=strlen(str); if(len==1) { printf("No Successor\n"); continue; } for(i=len-2;i>=0;i--) { if(str[i]<str[i+1]) { char t; int j=len-1; while(str[j]<=str[i]) j--; t=str[i]; str[i]=str[j]; str[j]=t; flag=1; qsort(str+i+1,len-i-1,1,cmp); break; } } if(flag) puts(str); else printf("No Successor\n"); } return 0; }
发表评论
-
UVa 10422 Knights in FEN
2012-09-07 08:40 942题目:http://uva.onlinejudge.org/i ... -
UVa 539 The Settlers of Catan
2012-08-31 22:22 28题目:http://uva.onlinejudge.org/i ... -
UVa 301 Transportation
2012-08-31 22:10 34题目:http://uva.onlinejudge.org/i ... -
UVa 639 Don't Get Rooked
2012-08-30 23:01 856题目:http://uva.onlinejudge.org/i ... -
UVa 216 Getting in Line
2012-08-29 20:48 767题目:http://uva.onlinejudge.org/i ... -
UVa 10474 Where is the Marble?
2012-08-28 13:45 886题目:http://uva.onlinejudge.org/i ... -
UVa 592 Island of Logic
2012-08-27 11:05 1686题目:http://uva.onlinejudge ... -
UVa 11205 The broken pedometer
2012-08-25 17:28 1096题目:http://uva.onlinejudge.org/i ... -
UVa 131 The Psychic Poker Player
2012-08-24 22:28 911题目:http://uva.onlinejudge.org/i ... -
UVa 729 The Hamming Distance Problem
2012-08-24 12:18 738题目:http://uva.onlinejudge.org/i ... -
Uva 10098 Generating Fast
2012-08-23 15:28 693题目:http://uva.onlinejudge.org/i ... -
UVa 10167 Birthday Cake
2012-08-16 20:57 642题目:http://uva.onlinejudge.org/i ... -
UVa 10129 Play on Words
2012-08-15 22:49 1186题目:http://uva.onlinejudge.org/i ... -
UVa 10596 Morning Walk
2012-08-14 22:05 923题目:http://uva.onlinejudge.org/i ... -
Uva 10305 Ordering Tasks
2012-08-13 23:40 701题目:http://uva.onlinejudge.org/i ... -
Uva 10004 Bicoloring
2012-08-13 23:34 918题目:http://uva.onlinejudge.org/i ... -
Uva 532 Dungeon Master
2012-08-13 23:29 829题目:http://uva.onlinejudge ... -
Uva 439 Knight Moves
2012-08-11 22:24 700题目:http://uva.onlinejudge.org/i ... -
UVa 784 Maze Exploration
2012-08-11 14:09 891题目:http://uva.onlinejudge.org/i ... -
Uva 572 Oil Deposits
2012-08-11 11:43 790题目:http://uva.onlinejudge.org/i ...
相关推荐
### SMD-Codes:主动型SMD半导体组件的标记代码 #### 概述 随着电子产品技术的不断进步和发展,表面贴装技术(Surface Mount Technology,简称SMT)因其体积小、重量轻、易于自动化组装等优点,在电子产品的设计与...
为此,纠错码(Error-Correcting Codes, ECC)作为一项关键的技术手段,在减少数据传输过程中的错误方面发挥着基础性的作用。本书《代数编码在数据传输中的应用》由伊利诺伊大学厄巴纳-香槟分校电气与计算机工程系...
Error-Correcting Codes, by Professor Peterson, was originally published in 1961. Now, with E. J. Weldon, Jr., as his coauthor, Professor Peterson has extensively rewritten his material. The book ...
github-recovery-codes.txt
在这个名为"C++ Codes"的压缩包中,可能包含了各种C++编程的示例代码、练习项目或库,涉及了C++的多个方面,例如基础语法、类与对象、模板、异常处理、STL(标准模板库)等。 **C++基础语法** C++的基础语法包括...
Cracking Codes with Python: An Introduction to Building and Breaking Ciphers (True PDF)
在这个名为"UVa_codes"的压缩包文件中,我们可以推测它包含了作者解决过的UVa问题的C++代码。 在C++编程领域,UVa问题的解决通常涉及到以下知识点: 1. **基础语法**:C++的基础语法是解题的基础,包括变量声明、...
- **克尔多克码(Kerdock Codes)**与**预备拉塔码(Preparata Codes)**:这两类码具有良好的非线性性质,适合于某些特定的应用场景。 - **自对偶码(Self-Dual Codes)**:这类码具有独特的数学性质,在编码理论中占有...
### 低密度奇偶校验码 (Low Density Parity Check Codes) #### 概述 低密度奇偶校验码(Low Density Parity Check Codes,简称LDPC码)是一种高效的线性错误校正码,最初由罗伯特·G·加拉格尔(Robert G. ...
标题中的“MATLAB Codes for Finite Element Analysis”表明这是一个关于使用MATLAB进行有限元分析的资源。有限元分析(Finite Element Analysis, FEA)是一种数值计算方法,常用于工程领域,如结构力学、流体力学等...
codes for collaborative filtering, which enables us to efficiently make recommendations with time complexity that is independent of the total number of items. We propose to construct binary codes for ...
【描述】"fk fk2_codes 2_codes fk2_codes fk2_codes fk2_codes fk2_codes fk2_codes"看起来像是重复的关键词,"fk"可能是缩写,可能是开发者的名字、项目代号或者是某种编程概念的简写。"2_codes"可能表示第二版...
涡轮码(Turbo Codes)是一种纠错编码技术,它在通信和存储系统中扮演着重要的角色,因其接近香农极限的性能而闻名。MATLAB是一个强大的数学计算软件,广泛用于科学计算、工程仿真以及信号处理等领域。在这个"turbo ...
错误校正码(Error-Correcting Codes, ECC)是信息理论中的一个基础概念,它们在数字通信和存储领域扮演着至关重要的角色。为了确保数据在传输或存储过程中遭受干扰时,接收方能够准确还原发送方的信息,错误校正码...
Windows Message Codes(系统消息代码)
《Variable-length Codes for Data Compression》是一本关于数据压缩领域中变长编码技术的专业书籍。本书由David Salomon教授撰写,详细介绍了各种变长编码算法及其在实际数据压缩场景中的应用。 #### 什么是变长...
错误纠正编码(Error-Correcting Codes,ECC)是通信和数据存储领域中至关重要的技术,旨在检测并修复数据传输或存储过程中可能出现的错误。《Fundamentals of Error-Correcting Codes》这本书由W. Cary Huffman撰写...
文档DSP0239 1.9.0详细阐述了MCTP协议中使用的各种ID和代码,这些ID和代码对于正确识别和解析MCTP消息至关重要。例如,它们可能包括消息类型标识、源和目标设备标识、命令和响应代码等。这些标识符和代码的标准化...