poj 3617 Best Cow Line 贪心

缘起

日常水题. poj 3617 Best Cow Line 是贪心法

分析

题意很裸

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
给你长度为N的字符串S, 要构造一个长度为N字符串T，起初T是空串, 随后反复进行如下操作
1. 从S的头部删除一个字符加到T的尾部
2. 从S的尾部删除一个字符加到T的尾部
请你输出合理采用上述策略能够构造出来的按字典序尽可能小的字符串

【输入】
第一行是一个正整数N (1<=N<=2000)
2...N+1每一行都是一个大写字母

【输出】
输出能够得到的字典序最小的字符串T

【样例输入】
6
A
C
D
B
C
B

【样例输出】
ABCBCD

【限制】
Time limit 1000 ms
Memory limit 65536 kB

贪心~ 每次取头尾较小的字符输出. 但是如果头尾相同的话, 则要继续比较才能知道到底输出哪一个字符.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

int n;
char s[2005];

int main() 
{

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	scanf("%d", &n);
	getchar();
	for (int i = 0; i<n;i++)
	{
		scanf("%c", s+i);
		getchar();
	}
	int x = 0, y = n-1,cnt = 0;
	while(x<=y)
	{
		if (s[x]<s[y])
		{
			putchar(s[x++]);
		}
		else if (s[x]>s[y])
		{
			putchar(s[y--]);
		}
		else // 如果s[x]==s[y]相等的话, 则要比较s[x++]和s[y--]
		{
			bool flag = true; // true表示采用左起的
			int xx = x,yy = y;
			while(xx<=yy&&s[xx]==s[yy])
			{
				xx++,yy--;
			}
			if (xx<yy&&s[xx]>s[yy]) // 发现要采用右起的情形
			{
				flag = false;
			}
			if (flag)
			{
				putchar(s[x++]);
			}
			else
			{
				putchar(s[y--]);
			}
		}
		cnt++;
		if (cnt%80==0) // 这里 PE 了2次, 没看清题目~ 
		{
			puts("");
		}
	}
	puts("");
	return 0;
}

ac情况

20748413 yfsyfs 3617 Accepted 296K 0MS G++ 781B 2019-08-16 09:04:50

此题在百练 oj 3377 上也提交过（百练 oj 3377），也ac了

影法师 Accepted 1332kB 843ms 838 B G++ 1分钟前