自动搬运

查看原文

来自洛谷，原作者为

	做梦想Peach **

搬运于2025-08-24 22:17:49，当前版本为作者最后更新于2020-09-19 21:32:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好久没发过题解了，正好这题是晚上模拟赛的一题，就来写一写咯。

这一题看上去显然是贪心，我们设两个指针，$a$ 表示头指针，也就是队列首端， $b$ 表示为指针，也就是队列末端。

下面是最好容易想到的策略：

1. 当 $\text{s[a]>s[b]}$ ，我们肯定是会选 $\text {s[b]}$ ，随之 $b- -$ 。
2. 当 $\text{s[a]<s[b]}$ ，我们肯定是会选 $\text {s[a]}$ ，随之 $a++$ 。

但是，通过样例我们发现，会出现 $\text {s[a]==s[b]}$ 情况，这种情况该怎么处理呢？

其实也很简单，我们找距离 $\text {s[a]}$ 和 $\text {s[b]}$ 最近的且不等于 $\text {s[a或b]}$ 的字符，再比较它们大小即可。

$\text {Code}:$

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
char s[3010];
int n,i,a,b,j,p,q;
int main () {
	scanf ("%d",&n);
	for (i=1;i<=n;i++)
		cin>>s[i];
	a=1;
	b=n;
	for (i=1;i<=n;i++) {//从i开始枚举。
		for (j=i;j<=i+79&&j<=n;j++) {//每80个字符就换行。
			if (s[a]==s[b]) {
				p=a;
				q=b;
				while (s[p]==s[q]) {
					p++;
					q--;
				}//策略3。
				if (s[p]<=s[q]) {
					printf ("%c",s[a]);
					a++;
				} //这里又可以想到上面最简单的两种策略。
				else {
					printf ("%c",s[b]);
					b--;
				}
			}
			else {
				if (s[a]>s[b]) {
					printf ("%c",s[b]);
					b--;//策略1。
				} 
				else {
					printf ("%c",s[a]);
					a++;//策略2。
				}
			}
		}
		i+=79;//继续搜索下面的80个字符。
		puts ("");
	}
	return 0;
}