题目: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 903题目: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 815题目:http://uva.onlinejudge.org/i ... -
UVa 216 Getting in Line
2012-08-29 20:48 724题目:http://uva.onlinejudge.org/i ... -
UVa 10474 Where is the Marble?
2012-08-28 13:45 851题目:http://uva.onlinejudge.org/i ... -
UVa 592 Island of Logic
2012-08-27 11:05 1644题目:http://uva.onlinejudge ... -
UVa 11205 The broken pedometer
2012-08-25 17:28 1051题目:http://uva.onlinejudge.org/i ... -
UVa 131 The Psychic Poker Player
2012-08-24 22:28 876题目:http://uva.onlinejudge.org/i ... -
UVa 729 The Hamming Distance Problem
2012-08-24 12:18 696题目:http://uva.onlinejudge.org/i ... -
Uva 10098 Generating Fast
2012-08-23 15:28 660题目:http://uva.onlinejudge.org/i ... -
UVa 10167 Birthday Cake
2012-08-16 20:57 606题目:http://uva.onlinejudge.org/i ... -
UVa 10129 Play on Words
2012-08-15 22:49 1128题目:http://uva.onlinejudge.org/i ... -
UVa 10596 Morning Walk
2012-08-14 22:05 882题目:http://uva.onlinejudge.org/i ... -
Uva 10305 Ordering Tasks
2012-08-13 23:40 660题目:http://uva.onlinejudge.org/i ... -
Uva 10004 Bicoloring
2012-08-13 23:34 877题目:http://uva.onlinejudge.org/i ... -
Uva 532 Dungeon Master
2012-08-13 23:29 790题目:http://uva.onlinejudge ... -
Uva 439 Knight Moves
2012-08-11 22:24 656题目:http://uva.onlinejudge.org/i ... -
UVa 784 Maze Exploration
2012-08-11 14:09 828题目:http://uva.onlinejudge.org/i ... -
Uva 572 Oil Deposits
2012-08-11 11:43 746题目:http://uva.onlinejudge.org/i ...
相关推荐
Common Flash Interface (CFI) ID Codes
C++ CodesC++ CodesC++ CodesC++ CodesC++ CodesC++ CodesC++ CodesC++ Codes
codes.zipcodes.zipcodes.zipcodes.zip
Fountain codes are record-breaking sparse-graph codes for channels with erasures, such as the internet, where files are transmitted in multiple small packets, each of which is either received without ...
Introduction to LDPC codes
Low Density Parity Check Codes Robert G. Gallager 1963
由贴片器件代码查找型号 SMD-codes Active SMD semiconductor components marking codes
Wu Yufei的经典的turbo codes的matlab程序
codes
scancodes键盘扫描码!超赞的哦!
Java programming codes
Crypto NTE Error Codes
Introduction To Error Correcting Codes
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 ...
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 ...
Android安全codesAndroid安全codes
fk fk2_codes 2_codes fk2_codes fk2_codes fk2_codes fk2_codes fk2_codes
Fundamentals of Error-Correcting Codes
Matlab codes for analysis numerical