主题：第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个回复）
141 楼
dert [专家分：0] 发布于 2009-03-04 20:46:00
//后来看看发现前面的一贴考虑得不够周到，故再发一贴。
#include <stdio.h>
#include<string.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int i=0,n=0,m=0;
char k=b[0],p[MAXLEN+1];
if(c[0]!='\0') c[0]='\0'; //将串置空
while(a[i]!='\0')
{
if(a[i]<=k)
{
c[n]=a[i];
c[n+1]='\0'; //随时构成一个完整的串
n++;
}
else break;
i++;
}
strcat(c,b);
while(a[i]!='\0')
{
p[m++]=a[i++];
}
p[m]='\0';
strcat(c,p);
}
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;
}
142 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-05 00:53:00
140楼的错在12 22222223
141楼的错在12 21
143 楼
mo_0820 [专家分：50] 发布于 2009-03-05 10:20:00
//修改了，希望别出现错误了
#include <stdio.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int i,j,k=0,m,flag=1,flag1=1;
for(i=0,j=0;flag;j++,i++)
{ if(!b[i]) i=0;
for(;a[j]<=b[i]&&flag;j++)
{ if(!i&&a[j])
{ c[k]=a[j]; k++;
if(a[j]==b[0]) break;
}
if(!a[j])
{ for(m=i;b[m];m++)
{ if(b[m]<b[0])
{
flag1=0;break;
}
}
if(flag1)
{ for(m=0;;k++)
{ c[k]=b[m];
if(!b[m]) break;
m++;
}
}
else
{ for(m=i;;k++)
{ c[k]=b[m]; m++;
if(!b[m]) break;
}
for(m=0,k++;m<i;m++,k++) c[k]=b[m];
c[k]=0;
}
flag=0;
}
if(flag&&i)
{ if(a[j]<=b[0])
{ c[k]=a[j]; k++;
if(a[j]<b[i]) i=0;
}
else
{ for(m=0;;k++)
{ if(b[m])
{ c[k]=b[m];m++;
}
else
{ for(;;k++)
{ c[k]=a[j];
if(!a[j]) break;
j++;
}
break;
}
}
flag=0;
}
}
if(i) break;
}
144 楼
mo_0820 [专家分：50] 发布于 2009-03-05 10:20:00
if(flag)
{ if(a[j]>b[i])
{ if(b[i]<b[0])
{ for(m=i;;k++)
{ c[k]=b[m]; m++;
if(!b[m]) break;
}
for(m=0,k++;m<i;m++,k++) c[k]=b[m];
for(;;k++)
{ c[k]=a[j];
if(!a[j]) break;
j++;
}
flag=0;
}
else
{ for(m=0;;k++)
{ if(b[m])
{ c[k]=b[m]; m++;
}
else
{ for(;;k++)
{ c[k]=a[j];
if(!a[j]) break;
else j++;
}
break;
}
}
flag=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;
}
145 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-05 13:36:00
楼上的错在112255 222215
146 楼
improve [专家分：0] 发布于 2009-03-05 15:20:00
建议不要固定程序格式，每个人都有自己的想法，需要创建什么函数，创建多少个以及传递参数的方式，那样规定死了，非得按着那个套路去不爽，固定了思维模式，只要输出结果符合规格即可。我认为这样好一点，希望此建议能被采纳。
147 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-05 15:23:00
[quote]
建议不要固定程序格式，每个人都有自己的想法，需要创建什么函数，创建多少个以及传递参数的方式，那样规定死了，非得按着那个套路去不爽，固定了思维模式，只要输出结果符合规格即可。我认为这样好一点，希望此建议能被采纳。[/quote]
你如果有看清楚我在题目说的要求，你就会知道那个格式就是[color=FF0000]输入输出格式[/color]，那些人不按这个做，根本就连输出结果都错掉，别说什么规定不规定了
148 楼
mo_0820 [专家分：50] 发布于 2009-03-05 17:01:00
放弃了，原来好多情况都没考虑到！！！！！！！！
149 楼
Reversed [专家分：0] 发布于 2009-03-05 17:16:00
/*虽然知道代码错 但是举不出反例*/
#include <stdio.h>
#include <string.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
int find_first_bigger(char* str, char c) {
char* temp = str;
int len = 0;
while (*temp <= c && *temp != 0) {++temp; ++len;}
return len;
}
int find(char* str, char c) {
char* temp = str;
int len = 0;
while (*temp < c && *temp != 0) {++temp; ++len;}
return len;
}
bool compare(char* str1, char* str2, char end, int& equal_num) {
equal_num = 0;
char* temp1 = str1; char* temp2 = str2;
int flag1 = 0; int flag2 = 0;
while (*temp1 == *temp2 && *temp1 != end && *temp2 != 0) {
if (*temp1 == *str2) ++equal_num;
++temp1; ++temp2;
}
if (*temp1 == 0 || *temp1 == end) {flag1 = 1;}
if (*temp2 == 0) {flag2 = 1;}
while (flag1 == 1 && flag2 != 1 && *temp2 == *str1) ++temp2;
if (flag1 == 1 && flag2 != 1 && *temp2 < *str1) return true;
if (flag1 == 1 && flag2 != 1 && *temp2 > *str1) return false;
while (flag1 != 1 && flag2 == 1 && *temp1 == *str2) ++temp1;
if (flag1 != 1 && flag2 == 1 && *temp1 < *str2) return false;
if (flag1 != 1 && flag2 == 1 && *temp1 > *str2) return true;
if (*temp1 > *temp2)
return true;
else
return false;
}
inline void move(char* a, char* b, char* c,int fLen,int aLen,int bLen) {
memcpy(c, a, fLen);
memcpy(c + fLen, b, bLen);
memcpy(c + fLen + bLen, a + fLen, aLen - fLen + 1);
}
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int count = 0;
bool flag = true;
int big = find_first_bigger(a, *b);
char end = *(a + big);
int aLen = strlen(a);
int bLen = strlen(b);
int fLen = find(a, *b);
while (fLen < big) {
flag = compare(a + fLen, b, end, count);
if (flag == true) {
move(a, b, c, fLen, aLen, bLen);
return;
}
else {
int temp = fLen + count;
fLen = temp + find(a + temp, *b);
}
}
move(a, b, c, big, 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;
}
150 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-05 17:25:00
有时，出现这么多情况的根本原因是是算法选择不正确
我来回复
您所在位置：