POJ 3617 字典序最小

本文主要是介绍POJ 3617 字典序最小，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

错误解法：

例如 CBAC 得到的将是  CBAC 正确应为 CABC

错误原因 是 每次只比较 首尾两个元素 而忽略了总体字典序最小的问题

此种 当C相等时应继续比较 B A 进而选择右侧的C而不是当C相等时随便选取一个C

			for(i = 0, j = n-1; i <= j; ){if(S[i] < S[j]){//	res[count++] = S[i++]; putchar(S[i++]);}else{//	res[count++] = S[j--];putchar(S[j--]);}

scanf(" %c",&S[I]); 其中的换行符可以跳过 回车、空白符、换行

这里把正、反 看做两个字符串进行比较字典序，以确定当某位置字符相等时候 应该选择 哪个字符输出

#include<stdio.h>
#define MAX 100001 char S[MAX];
char res[MAX];
int n;
char c;
int main(){while(scanf("%d",&n)!=EOF){for(int i = 0; i < n; ++i){scanf(" %c",&S[i]);} int i, j;int count = 0;int a = 0, b = n-1;int flag = 0;while(a <= b){flag = 0;for(i = 0; a + i <= b; ++i){//当 字符相等时继续判断下一位 if(S[a+i] < S[b-i]){flag = 1;break;}else if(S[a+i] > S[b-i]){flag = 0;break;}}if(flag) putchar(S[a++]);elseputchar(S[b--]);++count;if(count == 80){count = 0;printf("\n");}}printf("\n");printf("\n");}return 0;}

这篇关于POJ 3617 字典序最小的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---