主题：第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个回复）
沙发
HeroSong [专家分：940] 发布于 2009-02-21 21:10:00
#include <stdio.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
#include <string.h>
#include <stdlib.h>
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int i,aLen,bLen;
char d[MAXLEN*2+1];
aLen=strlen(a);
bLen=strlen(b);
strcpy(c,b);
strcat(c,a);
for(i=1;i<=aLen;i++)
{
memmove(d,a,i);
memmove(&d[i],b,bLen);
memmove(&d[i+bLen],&a[i],aLen-i+1);//包括末尾的'\0'
if(strcmp(d,c)<0)strcpy(c,d);
//不用清空d,因为每次都是从d缓冲区的首部开始，且组合串长度都相等
}
}
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;
}
板凳
雨中飞燕 [专家分：18980] 发布于 2009-02-22 11:49:00
1楼的代码测试结果：
正确性：完全正确
[color=red]时间效率：极低下[/color]
空间效率：好
可读性：很好
3 楼
天国龙 [专家分：490] 发布于 2009-02-22 17:26:00
[code=c]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
inline void move(char* a, char* b, char* c,int i,int aLen,int bLen)
{
memmove(c,a,i);
memmove(&c[i],b,bLen);
memmove(&c[i+bLen],&a[i],aLen-i+1);//包括末尾的'\0'
}
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int i,aLen,bLen,k;
aLen=strlen(a);
bLen=strlen(b);
i=0;
while(i<aLen&&a[i]<=b[0])
i++;
if(a[i]<b[0]||i==0)
move(a,b,c,i,aLen,bLen);
else
{
k=1;
while(k<bLen&&b[k]==b[0])
k++;
if(k==bLen||b[k]>b[0])
move(a,b,c,i,aLen,bLen);
else
{
i--;
while(a[i]==b[0])
i--;
i++;
move(a,b,c,i,aLen,bLen);
}
}
}
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]
4 楼
雨中飞燕 [专家分：18980] 发布于 2009-02-22 18:16:00
3楼的代码和1楼的同样评价。。。
5 楼
ws0415 [专家分：3370] 发布于 2009-02-22 20:06:00
[code=c]
#include <stdio.h>
#define MAXLEN 100000
#include <string.h>
void deal(char* a, char* b, char* c)
{
char *p;
int pos=1;
int i=2;
int size_a=strlen(a);
int size_b=strlen(b);
char *p1,*p2;
if(*a>*b)
{
p1=a;
p2=b;
p=c;
while(*p++=*p2++);
p--;
while(*p++=*p1++);
*p=0;
return;
}
while(i<=size_a)
{
p1=b;
p2=&a[pos];
int j=pos;
while(*p1&&*p2)
{
if(*p1>*p2) {pos=i;break;}
else if(*p1==*p2)
{
if(p1==b+size_b-1) p1=&a[pos];
else p1++;
if(j<i-1) p2=&a[++j];
else if(j==i-1) p2=b;
else if(p2!=b+size_b-1) p2++;
else p2=&a[i];
}
else break;
}
i++;
}
p=a;
char *q=c;
char *pb=b;
i=0;
while(i<pos) *q++=a[i++];
while(*q++=*pb++);
q--;
while(i<size_a) *q++=a[i++];
*q=0;
}
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]
6 楼
天国龙 [专家分：490] 发布于 2009-02-22 20:46:00
[quote]3楼的代码和1楼的同样评价。。。[/quote]
这个。。效率应该不是一个数量级的吧，可以提供测评方法或数据吗？
7 楼
雨中飞燕 [专家分：18980] 发布于 2009-02-22 21:28:00
http://yzfy.org/dis/listpost.php?tid=980
你要在线测评的话可以去这里
三楼的代码没认真看，正确性方面其实是错的
8 楼
天国龙 [专家分：490] 发布于 2009-02-22 21:32:00
#include <stdio.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
inline void move(char* a, char* b, char* c,int i)
{
char *aa,*bb,*cc;
aa=a;
bb=b;
cc=c;
int j=i;
while(i-->0) *cc++=*aa++;
while(*cc++=*bb++);
cc--;
while(*cc++=*aa++);
*cc=0;
}
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int i,aLen,bLen,j,k;
char *aa;
aa=a;
//aLen=strlen(a);
//bLen=strlen(b);
i=0;
while(*aa&&*aa++<=*b)
i++;
if(*aa<*b||i==0)
move(a,b,c,i);
else
{
k=1;
aa=b;
while(*aa&&*aa++==*b);
if(!*aa||*aa>*b)
move(a,b,c,i);
else
{
i--;
aa=a;
while(*aa==*b)
i--;
i++;
move(a,b,c,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;
}
自己随便测试了下，发现主要慢在数组操作上，但比一楼还是快些，毕竟它复制了那么多次，我只复制一次，太久没有用C/C++，不习惯用指针了，参考了5楼的代码，按原来的算法修改成指针操作了，效率好多了！
9 楼
雨中飞燕 [专家分：18980] 发布于 2009-02-22 21:35:00
测试结果：
5楼和8楼的代码逻辑上不正确
10 楼
天国龙 [专家分：490] 发布于 2009-02-22 21:43:00
[quote]测试结果：
5楼和8楼的代码逻辑上不正确[/quote]
发完才看到你的回复，，，第一次错的，第二次也错了
我来回复
您所在位置：