正文
Best Cow Line---poj3617（贪心）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目链接：http://poj.org/problem?id=3617
题意：有n头牛.刚开始有一个序列.现在想要重新排列.每次从原始的序列头部和尾部取出一个取出一个放到新的序列尾部.最后使得得到的新序列字典序最小；
我们每次可以比较头部和尾部的两个字母，把字典序小的加入新的队列中去.如果相等的话找到一个最先能找到字典序小的那个放入新的序列中去;
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>using namespace std;#define N 2110
#define met(a, b) memset(a, b, sizeof(a))typedef long long LL;int n;
char s[N], T[N], ch;int compare(int L, int R)
{
if(s[L] == s[R])
{
while(s[L] == s[R] && L <= R)
L++, R--;
}
return s[L] < s[R];
}int main()
{ while(scanf("%d ", &n) != EOF)
{
for(int i=; i<n; i++)
scanf("%c%c", &s[i], &ch);
int L = , R = n-, k = ;
while(L <= R)
{
if(compare(L, R))
T[k++] = s[L++];
else
T[k++] = s[R--];
}
T[k] = '\0';
for(int i=; i<k; i++)
{
if(i%== && i!=)
printf("\n");
printf("%c", T[i]);
}
}
return ;
}
/*
6
A
C
D
B
C
BABCBCD
*/
