主题：第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个回复）
81 楼
雨中飞燕 [专家分：18980] 发布于 2009-02-26 12:21:00
很好，出现一个给我开大刀的机会了
82 楼
251316192 [专家分：0] 发布于 2009-02-26 15:40:00
#include <iostream>
#include <string>
using namespace std;
int main(void)
{
string a, b, c;
void deal(string & a, string & b, string & c);
while (cin >> a >> b) {
deal(a, b, c);
cout << c << endl;
}
return 0;
}
83 楼
251316192 [专家分：0] 发布于 2009-02-26 15:40:00
void deal(string & a, string & b, string & c) {
string::size_type length = a.size(), i, j;
i = 0;
j = length - 1;
while(i !=length) {
if(b[0] < a[i]) {
c = string(a).insert(i,b);
return ;
}
if(b[0] == a[i])
break;
++i;
}
while(j >= 0) {
if(b[0] > a[j]) {
if(j != length -1){
c = string(a).insert(i,b);
if(a[0] == b[0]) {
string temp(b+a);
if(c > temp)
c = temp;
return;
}
return ;
}
else {
c = a + b;
if(a[0] == b[0]) {
string temp(b+a);
if(c > temp)
c = temp;
return;
}
return ;
}
}
if(b[0] == a[j])
break;
--j;
}
string sub(a.substr(i,j - i + 1));
string::size_type LengthSub = sub.size(), m, n;
m = 0;
n = LengthSub - 1;
string tp0(sub), tp1(sub);
while(m !=LengthSub) {
if(b[0] < sub[m]) {
c = a.substr(0,i) + tp0.insert(m,b) + a.substr(j+1);
tp0 = sub;
if(b[0] != sub[m-1])
return ;
else {
if(m == 1)
tp1 = a.substr(0,i) + b + sub + a.substr(j+1);
else
tp1 = a.substr(0,i) + tp0.insert(m-1,b) + a.substr(j+1), tp0 = sub;
}
if(c > tp1)
c = tp1;
return ;
}
++m;
}
while(n >= 0) {
if(b[0] > sub[n]) {
c = a.substr(0,i) + tp0.insert(n+1,b) + a.substr(j+1);
tp0 = sub;
if(b[0] != sub[n+1])
return ;
else {
if(n == LengthSub - 2)
tp1 = a.substr(0,i) + sub + b + a.substr(j+1);
else
tp1 = a.substr(0,i) + tp0.insert(n+2,b) + a.substr(j+1), tp0 = sub;
}
if(c > tp1)
c = tp1;
return ;
}
if(n == 0)
break;
--n;
}
string::size_type l(0), LengthB(b.size());
while(l != LengthB) {
if(b[0] != b[l])
break;
++l;
}
if(l == LengthB) {
c = string(a).insert(i,b);
return ;
}
else {
if(b[l] < b[0]) {
c = a.substr(0,i) + b + sub + a.substr(j+1);
return ;
}
else {
c = a.substr(0,i) + sub + b + a.substr(j+1);
return ;
}
}
}
84 楼
雨中飞燕 [专家分：18980] 发布于 2009-02-26 16:04:00
987654321998877665544 98
楼上试试这个
85 楼
251316192 [专家分：0] 发布于 2009-02-26 16:46: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 length = a.size();
int i = 0;
int j = length - 1;
int k = length - 1;
string last;
while(i !=length) {
if(b[0] < a[i]) {
c = string(a).insert(i,b);
return c;
}
if(b[0] == a[i])
break;
++i;
}
if(i == length)
return c = a + b;
while( k >= 0) {
if(b[0] > a[k]) {
if(j != length -1){
last = string(a).insert(i,b);
break;
}
else {
last = a + b;
break;
}
}
--k;
}
while(j >= 0) {
if(b[0] == a[j])
break;
--j;
}
string sub(a.substr(i,j - i + 1));
int LengthSub = sub.size(), m, n;
m = 0;
n = LengthSub - 1;
string tp0(sub), tp1(sub);
while(m !=LengthSub) {
if(b[0] < sub[m]) {
c = a.substr(0,i) + tp0.insert(m,b) + a.substr(j+1);
tp0 = sub;
if(b[0] != sub[m-1])
break;
else {
if(m == 1)
tp1 = a.substr(0,i) + b + sub + a.substr(j+1);
else
tp1 = a.substr(0,i) + tp0.insert(m-1,b) + a.substr(j+1), tp0 = sub;
}
if(c > tp1)
c = tp1;
break;
}
++m;
}
while(n >= 0) {
if(b[0] > sub[n]) {
c = a.substr(0,i) + tp0.insert(n+1,b) + a.substr(j+1);
tp0 = sub;
if(b[0] != sub[n+1])
break;
else {
if(n == LengthSub - 2)
tp1 = a.substr(0,i) + sub + b + a.substr(j+1);
else
tp1 = a.substr(0,i) + tp0.insert(n+2,b) + a.substr(j+1), tp0 = sub;
}
if(c > tp1)
c = tp1;
break;
}
--n;
}
string::size_type l(0), LengthB(b.size());
while(l != LengthB) {
if(b[0] != b[l])
break;
++l;
}
if(l == LengthB) {
c = string(a).insert(i,b);
}
else {
if(b[l] < b[0]) {
c = a.substr(0,i) + b + sub + a.substr(j+1);
}
else {
c = a.substr(0,i) + sub + b + a.substr(j+1);
}
}
if(c > last)
c = last;
return c;
}
86 楼
雨中飞燕 [专家分：18980] 发布于 2009-02-26 17:28:00
嘛，你输入两个1后，好像没有东西啊
87 楼
zhaoyg [专家分：4790] 发布于 2009-02-26 19:53:00
*********
********
有写错了
88 楼
zhaoyg [专家分：4790] 发布于 2009-02-26 21:03:00
快吐血了！！！！！
这次再不对我他妈的就不活了！！！
#include <stdio.h>
#include <queue>
#include <string.h>
#define MAXLEN 100000
#define BEFORE 1
#define AFTER 0
#define GREATER 1
#define EQUAL 0
#define LESS -1
using std::queue;
bool Is_Greater_To_b0(const char *b)
{
//如果b中自左向右第一个不等于b[0]的字符小于b[0],则返回false , 否则返回true
int i;
for(i = 1 ; b[i] ;i++)
if (b[i] != b[0])
return b[0] < b[i] ? true : false;
}
int Compare(const char *current , const char *end,const char *b)
{
//
int i=0;
while ( end != current && b[++i] )
{
if ( *current != b[i] )
return *current > b[i] ? LESS : GREATER;
current++;
}
if ( end == current )
{
for ( ; b[++i] ; )
{
/*
if (b[i] > b[0])
return GREATER;
if (b[i] <= b[0])
return LESS;
*/
return b[0] >= b[i] ? LESS : GREATER;
}
}
return GREATER;
}
void deal(char* a, char* b, char* c)
{
const char *current , *begin , *end ,*brk_point;
queue<const char*> positionset;
begin = a;
end = a+strlen(a);
brk_point = NULL;
memset(c , 0 , MAXLEN*2+1);
for (current = begin ; current != end ; current++)
{
if ( b[0] < *current)
{
end = current;
break;
}
if ( b[0] == *current)
{
positionset.push(current);
}
}
if (positionset.empty() || Is_Greater_To_b0(b))
{
brk_point = end;
}
else
{
//positionset is not empty
int i;
int temp;
while ( 1 )
{
if (positionset.empty())
{
brk_point = end;
break;
}
current = positionset.front();
positionset.pop();
temp = Compare(current+1,end, b);
if ( GREATER == temp )
continue;
if( LESS == temp )
{
brk_point = current;
break;
}
}
}
memcpy(c , a , brk_point - a);
c[brk_point - a] = '\0';
memcpy(c+strlen(c) , b , strlen(b)+1);
memcpy(c+strlen(c) , brk_point , a+strlen(a) - brk_point);
}
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;
}
89 楼
雨中飞燕 [专家分：18980] 发布于 2009-02-26 23:00:00
你说说你的算法吧？
90 楼
蓝桥小帽 [专家分：0] 发布于 2009-02-27 00:21:00
#include <stdio.h>
#include <assert.h>
#include <string.h>
#define MAXLEN 100000
void deal(char* a,char* b,char* c)
{
char *ptr_a,*ptr_b,*temp;
int equal_before = 0;
int len_a,len_b,minus;
ptr_a = a;
ptr_b = b;
temp = ptr_a;
assert(a!=NULL && b!=NULL && c!=NULL);
if((*ptr_a == '\0')||(*ptr_b == '\0'))
return;
while( *temp != '\0')
{
if(*ptr_a < *ptr_b)
{
temp++;
ptr_a = temp;
ptr_b = b;
equal_before = 0;
}
else if( *ptr_a > *ptr_b)
{
if(equal_before == 1)
ptr_a = temp;
break;
}
else
{
ptr_a++;
ptr_b++;
if( (*ptr_a == '\0')||(*ptr_b == '\0'))
{
temp++;
ptr_a = temp;
ptr_b = b;
equal_before = 0;
}
else
{
equal_before = 1;
}
}
}
/* copy*/
len_a = strlen(a);
len_b = strlen(b);
minus = ptr_a - a;
if( minus==0)/*beg*/
{
strcpy(c,b);
strcpy(c+len_b,a);
}
else if( minus== len_a)/*end*/
{
strcpy(c,a);
strcpy(c+len_a,b);
}
else if( minus >0 && minus<(len_a-1))
{
strncpy(c,a, minus);
strcpy(c+minus,b);
strcpy(c+minus+len_b,a+minus);
}
}
char a[MAXLEN+1],b[MAXLEN+1],c[MAXLEN+1];
int main(void)
{
while(scanf("%s%s",a,b)!=EOF)
{
deal(a,b,c);
puts(c);
}
return 0;
}
我来回复
您所在位置：