poj 3617 Best Cow Line 解题报告
2024-09-03 05:48:41
题目链接:http://poj.org/problem?id=3617
题目意思:给出一条长度为n的字符串S,目标是要构造一条字典序尽量小,长度为n的字符串T。构造的规则是,如果S的头部的字母 < S的尾部的字母,那么将S的头部的字母加入到T中,删除S的头部的字母;如果S的头部的字母 > S的尾部的字母,那么将S的尾部的字母加入到T中,删除S的尾部的字母。
这个题目的关键是如何处理 S 的头部的字母(假设用 i 指示) = S的尾部的字母(j) 这种情况。此时需要比较 i+1 和 j-1 的位置的字母,如果相同,继续比较下去。
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std; const int maxn = + ;
char s[maxn]; int main()
{
int n, i, j, a, b, cnt;
while (scanf("%d", &n) != EOF)
{
for (i = ; i < n; i++)
{
getchar();
scanf("%c", &s[i]);
}
cnt = ;
i = , j = n-;
while (i <= j)
{
if (s[i] < s[j] && i <= j)
printf("%c", s[i++]);
else if (s[i] > s[j] && i <= j)
printf("%c", s[j--]);
else
{
a = i;
b = j;
while (s[i] == s[j] && i < j)
{
i++;
j--;
}
if (s[i] <= s[j] || i == j) // s[i] <= s[j] 不能写成s[i] < s[j],这是为了处理aaaaa这些情况,否则改了会输出a
{
printf("%c", s[a]);
j = b;
i = a+;
}
else if (s[i] > s[j])
{
printf("%c", s[b]);
i = a;
j = b-;
}
printf("a = %d, b = %d, i = %d, j = %d\n", a, b, i, j);
}
cnt++;
if (cnt % == )
putchar('\n');
}
}
return ;
}
相反,别人写的,不需要考虑太多琐碎的情况
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std; const int maxn = + ;
char s[maxn]; int main()
{
int n, i, a, b;
while (scanf("%d", &n) != EOF)
{
for (i = ; i < n; i++)
{
getchar();
scanf("%c", &s[i]);
}
int cnt = ;
a = , b = n-;
while (a <= b)
{
bool left = false;
for (i = ; 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)
printf("%c", s[a++]);
else
printf("%c", s[b--]);
cnt++;
if (cnt % == )
putchar('\n');
}
}
return ;
}
最新文章
- [Cordova] 手机网页里的1px
- Xcode8 适配iOS10时遇见的一些问题
- Oracle数据类型隐式转换小析
- Android开发之Intent略解
- CentOS的网络配置(终端环境)
- CodeForces - 416A (判断大于小于等于 模拟题)
- sqlserver中常用的全局变量
- Liferay 6开发学习(二十六):数据库连接相关问题
- AS与JS相互通信(Flex中调用js函数)
- 将文件的图标添加到LISTVIEW中
- iOS 更改导航栏返回button文字
- python 从数据库表生成model
- Android中获取网页表单中的数据
- Android搜索芽发展clientVersion1.0结束(过程和结果显示)
- Lodop打印控件打印机可打区域的影响 设置纸张边缘为基点
- 爬虫系列5:scrapy动态页面爬取的另一种思路
- 利用WCF搭建RESTful--纯代码启动
- [技术] OIer的C++标准库 : 字符串库
- django model form 保存方法 django-rest-framework save 修改某一项值 方法
- vs2012配置