voip
风的方向
厚德致远,博学敦行!
posts - 52,comments - 21,trackbacks - 0
         苦恼啊!

Description

设有n个正整数,将他们连接成一排,组成一个最大的多位整数。例如:n=3时,3个整数13,312,343,连成的最大整数为:34331213

又如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613

Input

N
N个数

Output

连接成的多位数

Sample Input

3
13 312 343
0

 

Sample Output

34331213
      这个题目意思应该很好理解,至少会想有两种解题思路,
         一、把数组从大到小排列,这样是最大吗?  显然不是,例如:123 9,应该输出9123;
         二、把数组按字符串排序,这样是最大吗?这问题可能会然我们困惑,但是这也是错的,例如:120,12;应该输出12120;
这个题目不知道毒害了多少人(当然我指的是ACM新人),尤其是第二种思路去写代码的。。这只是一个悲剧的开始,你把一条弯路在直走!
其实这个题目应该是属于动态规划的最简单应用!子问题,给你两个数,让你连成最大数,一定非常简单,只能组成两个数,比较一下大小就成!这就是解题思路!
如果给你三个数呢?一直递推下去!悲剧啊,尽然怎么简单!
代码如下:


#include
<stdio.h>
#include
<string.h>
#include
<stdlib.h>

int main()
{
    
int n,i,j,l,k;
    
char s[1000][100];
    
char s1[200],s2[200];
    
while(scanf("%d",&n)!=EOF&&n!=0)
    
{
        
for(i=0;i<n;i++)
        
{
            scanf(
"%s",s[i]);
            
while(s[i][0]=='0')
            
{
                
if(strlen(s[i])==1)
                    
break;
                strcpy(s[i],s[i]
+1);
            }

        }

        
for(i=0;i<n;i++)
        
{            
            
for(j=i+1;j<n;j++)
            
{
                strcpy(s1,s[i]);
                strcat(s1,s[j]);
                strcpy(s2,s[j]);
                strcat(s2,s[i]);
                
if(strcmp(s1,s2)<0)
                
{
                    strcpy(s1,s[i]);
                    strcpy(s[i],s[j]);
                    strcpy(s[j],s1);
                }

            }

        }

        
for(i=0;i<n;i++)
        
{
            
if(s[0][0]=='0')
            
{
                printf(
"0");
                
break;
            }

            
else
            
{
                printf(
"%s",s[i]);
            }

        }

        printf(
"\n");
    }

    
return 0;
}



本来我也是第二种思路的,我看了感觉不像,因为以前写过了!
早上的几点收获:
1、<string>头文件和<string.h>头文件是不一样的!运行时的一个错误,弄了一个早上,最后发现这什么个问题!
2、运用容器,排序字符串
 
    vector<string> words;
    
string str;
    
while(scanf("%s",str)!=EOF)  
        words.push_back(str);

    sort(words.begin(),words.end(),greater
<string>());


    
for(vector<string>::size_type i=0;i<words.size();i++)
    
{
            cout
<<words[i]<<endl;
    }

不过会有很多警告,让我很苦恼!有谁知道呢?
警告如下:
--------------------Configuration: rongqi - Win32 Debug--------------------
Compiling
rongqi.cpp
c:\documents and settings\administrator\桌面\rongqi\rongqi.cpp(
81) : warning C4786: 'std::reverse_iterator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > const *,std::basic_string<char,std::char_traits<char>,std::allocator<char
> >,std::basic_string<char,std::char_traits<char>,std::allocator<char> > const &,std::basic_string<char,std::char_traits<char>,std::allocator<char> > const *,int>' : identifier was truncated to '255' characters in the debug information
c:\documents and settings\administrator\桌面\rongqi\rongqi.cpp(81) : warning C4786: 'std::reverse_iterator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > *,std::basic_string<char,std::char_traits<char>,std::allocator<char> >,st
d::basic_string<char,std::char_traits<char>,std::allocator<char> > &,std::basic_string<char,std::char_traits<char>,std::allocator<char> > *,int>' : identifier was truncated to '255' characters in the debug information
c:\program files\microsoft visual studio\vc98\include\vector(39) : warning C4786: 'std::vector<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::allocator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > >
 >::vector<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::allocator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > > >' : identifier was truncated to '255' characters in the debug information
c:\program files\microsoft visual studio\vc98\include\vector(60) : warning C4786: 'std::vector<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::allocator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > >
 >::~vector<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::allocator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > > >' : identifier was truncated to '255' characters in the debug information

rongqi.obj 
- 0 error(s), 0 warning(s)
3、在程序头上写#pragma   warning  (disable:   4786),可以注销4786以后警告!
posted on 2010-09-06 11:52 jince 阅读(829) 评论(0)  编辑 收藏 引用 所属分类: Questions

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


哈哈哈哈哈哈