苦恼啊!
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新人),尤其是第二种思路去写代码的。。这只是一个悲剧的开始,你把一条弯路在直走!
其实这个题目应该是属于动态规划的最简单应用!子问题,给你两个数,让你连成最大数,一定非常简单,只能组成两个数,比较一下大小就成!这就是解题思路!
如果给你三个数呢?一直递推下去!悲剧啊,尽然怎么简单!
代码如下:
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int n,i,j,l,k;
char s[1000][100];
char s1[200],s2[200];
while(scanf("%d",&n)!=EOF&&n!=0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%s",s[i]);
while(s[i][0]=='0')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(strlen(s[i])==1)
break;
strcpy(s[i],s[i]+1);
}
}
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j=i+1;j<n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
strcpy(s1,s[i]);
strcat(s1,s[j]);
strcpy(s2,s[j]);
strcat(s2,s[i]);
if(strcmp(s1,s2)<0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
strcpy(s1,s[i]);
strcpy(s[i],s[j]);
strcpy(s[j],s1);
}
}
}
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(s[0][0]=='0')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("0");
break;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("%s",s[i]);
}
}
printf("\n");
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
本来我也是第二种思路的,我看了感觉不像,因为以前写过了!
早上的几点收获:
1、<string>头文件和<string.h>头文件是不一样的!运行时的一个错误,弄了一个早上,最后发现这什么个问题!
2、运用容器,排序字符串
vector<string> words;
string str;
while(scanf("%s",str)!=EOF)
words.push_back(str);
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
sort(words.begin(),words.end(),greater<string>());
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
for(vector<string>::size_type i=0;i<words.size();i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
cout<<words[i]<<endl;
}
不过会有很多警告,让我很苦恼!有谁知道呢?
警告如下:
--------------------Configuration: rongqi - Win32 Debug--------------------
Compiling![](http://www.cppblog.com/Images/dot.gif)
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
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
rongqi.obj - 0 error(s), 0 warning(s)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
3、在程序头上写#pragma warning (disable: 4786),可以注销4786以后警告!
posted on 2010-09-06 11:52
jince 阅读(855)
评论(0) 编辑 收藏 引用 所属分类:
Questions