主题：第80次编程比赛（08第二学期开学第一炮）
雨中飞燕 [专家分：18980] 发布于 2009-02-21 18:44:00
原79次冠军因长时间不再发帖子，故本次由本人开展
[color=0000FF]题目描述：[/color]
现在，有两个正整数A和B，例如A是345，B是478，现在，需要把B插入到A里，
而A有三位，所以有四个位置选择，所得结果分别是：
478345, 347845, 344785, 345478
我们通过对比可以知道，在这当中最小的一个是344785
这两个正整数长度不超过100000位，各个位均不包含数字0
现在的目标是，要找出插入后所能得到的最小的整数，输出这个整数
[color=0000FF]样例输入：[/color]
345 478
12345 678
12 21
12 23
[color=0000FF]样例输出：[/color]
344785
12345678
1212
1223
[color=0000FF]答题要求：[/color]
请完善以下代码(C/C++均可)：
[code=c]#include <stdio.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
}
char a[MAXLEN+1], b[MAXLEN+1], c[MAXLEN*2+1];
int main(void)
{
while (scanf("%s%s", a, b)!=EOF)
{
deal(a, b, c);
puts(c);
}
return 0;
}[/code]
其它信息：
本次比赛以公开答题代码的形式，且附以及时的测试，允许直接在本帖子讨论算法
测试内容：正确性，时间效率，空间效率，代码可读性
本次比赛结束时间3月8日 23:00
[color=FF0000]在本帖子回复广告或比赛无关内容者立即封ID及IP[/color]
最后更新于：2009-02-22 11:57:00
回复列表 （共182个回复）
71 楼
雨中飞燕 [专家分：18980] 发布于 2009-02-25 21:05:00
69楼的试试 98 991
70楼的试试 8787868687 8787868687
72 楼
maths_dxj [专家分：90] 发布于 2009-02-25 23:23:00
[code=c]
#include <stdio.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
void deal(char* a, char* b, char* c)
{
int i = 0;
int k = 0;
int idx = 0;
while (a[i] != '\0') {
idx = i;
if (a[i] < b[0]) {
c[k] = a[i];
} else if (a[i] == b[0]) {
int add = 0;
while (b[add] != '\0' && a[i + add] != '\0') {
if (a[add + i] <= b[0]) {
add++;
} else {
break;
}
}
bool f = true;
for (int id = 0; id < add; id++) {
int delta = a[i + id] - b[id];
if (delta == 0) {
continue;
}
f = false;
if (delta < 0) {
idx = add;
}
break;
}
if (f && b[add] != '\0') {
if (b[add] < b[0]) {
idx = 0;
} else {
idx = add;
}
}
add = idx;
for (int u = 0; u < add; u++) {
c[k++] = a[u + i];
}
i += add;
break;
} else {
break;
}
i++;
k++;
}
int r = 0;
while (b[r] != '\0') {
c[k++] = b[r++];
}
while (a[i] != '\0') {
c[k++] = a[i++];
}}
char a[MAXLEN+1], b[MAXLEN+1], c[MAXLEN*2+1];
int main(void)
{
while (scanf("%s%s", a, b)!=EOF)
{
deal(a, b, c);
puts(c);
}
return 0;
}
[/code]
73 楼
251316192 [专家分：0] 发布于 2009-02-25 23:24:00
#include <iostream>
#include <string>
using namespace std;
int main(void)
{
string a, b, c;
string deal(string a, string b, string c);
while (cin >> a >> b) {
cout << deal(a, b, c) << endl;
}
return 0;
}
string deal(string a, string b, string c) {
int i = 0;
int sentry = 1;
while(i != a.size()) {
if(b[0] < a[i]) {
sentry = -1;
break;
}
else if(b[0] == a[i]) {
sentry = 0;
break;
}
++i;
}
if(sentry == -1)
c = string(a).insert(i,b);
if(sentry == +0) {
if(a.size() == 1) {
string tp1(a), tp2;
tp1 += b;
tp2 = b + a;
c = tp1 > tp2? tp2 : tp1;
}
else {
string tp1(a), tp2;
tp1.insert(i,b);
if(i == a.size())
tp2 += b;
else {
tp2 = a[0] + deal(a.substr(1), b, c);
}
c = tp1 > tp2? tp2 : tp1;
}
}
if(sentry == +1)
c = a + b;
return c;
}
74 楼
雨中飞燕 [专家分：18980] 发布于 2009-02-25 23:35:00
72楼的代码有个低级错误，你把C数组的声明放在main里面看看什么结果
73楼的试试12 23
75 楼
251316192 [专家分：0] 发布于 2009-02-26 00:04:00
#include <iostream>
#include <string>
using namespace std;
int main(void)
{
string a, b, c;
string deal(string a, string b, string c);
while (cin >> a >> b) {
cout << deal(a, b, c) << endl;
}
return 0;
}
string deal(string a, string b, string c) {
int i = 0;
int sentry = 1;
while(i != a.size()) {
if(b[0] < a[i]) {
sentry = -1;
break;
}
else if(b[0] == a[i]) {
sentry = 0;
break;
}
++i;
}
if(sentry == -1)
c = string(a).insert(i,b);
if(sentry == +0) {
if(a.size() == 1) {
string tp1(a), tp2;
tp1 += b;
tp2 = b + a;
c = tp1 > tp2? tp2 : tp1;
}
else {
string tp1(a), tp2(a);
tp1.insert(i,b);
if(i == a.size() - 1)
tp2 += b;
else {
tp2 = a.substr(0,i+1) + deal(a.substr(i+1), b, c);
}
c = tp1 > tp2? tp2 : tp1;
}
}
if(sentry == +1)
c = a + b;
return c;
}
76 楼
bai_wx [专家分：0] 发布于 2009-02-26 09:20:00
[quote]987987 987986这个错了
65楼的代码是没改过的吗？[/quote]
代码经过修改，上述输入的输出是987986987987
77 楼
bai_wx [专家分：0] 发布于 2009-02-26 09:33:00
此外，2楼以及类似程序输入为1357和2468时的输出是12468357，而不是12345678
希望楼主能附加一个测试序列
78 楼
雨中飞燕 [专家分：18980] 发布于 2009-02-26 10:01:00
[quote]此外，2楼以及类似程序输入为1357和2468时的输出是12468357，而不是12345678
希望楼主能附加一个测试序列[/quote]
如果你的理解是后者，那你就是理解题目错误
那个测试数据不是对你说的，我说你没修改过的意思是，我之前对你说的那组数，错的还是错
123 123这组的结果不是112233，根本没有这个结果
答案是112323，请理解清楚题意
79 楼
bai_wx [专家分：0] 发布于 2009-02-26 11:20:00
我理解错题目了，浪费版主您的宝贵时间了，见谅
80 楼
317187479 [专家分：0] 发布于 2009-02-26 12:11:00
````刚创建了个编程技术交流群``````
新手和爱学习的友友请加```群号：57842577
我也不懂````大家一起学习``
我来回复
您所在位置：