练习题 No.4 字典序最小问题（贪心法）

要求

给定长度为N的字符串S，要构造一个长度为N的字符串T。起初，T是一个空串，随后反复进行下列任意操作。 1. 从S的头部删除一个字符，加到T的尾部。 2. 从S的尾部删除一个字符，加到T的尾部

输入格式

第一行输入一行字符串

输出格式

输出字符串T

测试输入

ACDBCB

测试输出

ABCBCD

解题思路

此题用贪心法，从头或者尾选一个较小的。 比较头尾的二个字符大小，将加的移除到T中，如果相等，则进行下一个字符判断，直到发现有大小不同的，如果全相同，则无论移除的是头还是尾都一样。

代码

#include<iostream> #include<string> #include<sstream> using namespace std; int main() { string str; string str2; getline(cin, str); ostringstream is(str2); int size = str.length(); int head = 0; int tail = size - 1; bool left = false; while ( head <= tail) { left = false; for (int i = 0; head + i <= tail; i++) { if (str[head + i] < str[tail - i]) { left = true; break; } else if (str[head + i] > str[tail - i]){ left = false; break; } } if (left) { is << str[head++]; } else { is << str[tail--]; } } cout << is.str() << endl; return 0; }