Best Cow Line （POJ3617）

给定一个长度为N的字符串S，要构建一个长度为N的字符串T。起初T是一个空的字符串，随后重复进行一下任意操作；

从S的头删除一个字符添加到T的尾部

从S的尾部删除一个字符添加到T的尾部

目的：

使得T的字典序尽可能小

*字典序字典序是从前到后比较两个字符串大小的方法， 首先比较第一个字符，如果不同，则第一个字符较小的字符串更小，如果相同则继续比较第二个字符.......如此继续，比较整个字符串的大小

 

// 贪心算法2 P 42
//

#include "stdafx.h"
#include<iostream>
#include<math.h>
#include <algorithm>
#define MAX_N 6
using namespace std;
int N=6;
char S [MAX_N+1];
int a = 0;
int b = N - 1;
void solve() {
	while (a <= b) {
		bool left = false;
		for (int i = 0; a + i <= b; i++)
		{
			if (S[a + i] < S[b - i]) {
				left = true;
				break;
			}
			else if (S[a + i] > S[b - i]) {
				left = false;
				break;
			}
		}
		if (left) putchar(S[a++]);
		else putchar(S[b--]);

	}
	putchar('\n');
}

int main()
{
	cout << "please input S\n";
	cin >> S;
	cout << "this is T\n";
	solve();
	cout << S << endl;
	while (1);
	
    return 0;
}