淘汰赛神农百草题解

题解"/>

淘汰赛神农百草题解

题目：

神农百草

时间限制: C/C++ 2000ms; Java 4000ms 内存限制: 4914406KB

问题描述

《纲鉴易知录》：民有疾，未知药石，炎帝（神农氏）始草木之滋，察其寒、温、平、热之性，辨其君、臣、佐、使之义，尝一日而遇七十毒，神而化之，遂作文书上以疗民族，而医道自此始矣。

神农遇见了一位中毒的病人，现在他有n中药材，每种药材的价值是一串数字来表示，现在他为了救这个病人，需要把这些药材按一定的顺序放入药炉里，为病人做出解药。

现有a、b两种药材，a的价值为99973，b的价值为9999，当神农把a药材和b药材按照一定顺序放入药炉时，先放a再放b得到药的价值为999739999，而先放b再放a的价值为999999973.

神农要想100%的解掉这位病人的毒，只能让自己的药材制成的解药的价值最大，现在他请你来帮他解决这个问题

输入描述

第一行一个数n（1<=n<=1000000）

接下来n行每行一串数字s[i]( |s[i]|<=10000 )

输出描述

解药的最大价值

样例输入

2
99973
9999

样例输出

999999973

题意：简而言之，给出n个字符串（字符串长度小于10000），如何拼接才能使这个最后的数值最大。

思路：首先这个是大整数类。核心代码：

bool cmp(string x,string y){return x+y>y+x;
}

感觉sort排序很神奇，竟然也能直接对string类型的排序。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<sstream>
#include<stack>
#define INF 0x3f3f3f
typedef long long ll;using namespace std;
const int maxn=1000000+10;
string a[maxn];bool cmp(string x,string y){return x+y>y+x;
}int main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n,cmp);for(int i=0;i<n;i++)cout<<a[i];cout<<"\n";return 0;
}

心得：

淘汰赛自己过了4题，有一点高兴吧。4题是学长给的最低要求，虽然自己排名也不是很高，因为本来就是抱着被淘汰的结局去的，不过还好，没有辜负自己暑假40天的训练。深知自己还是小白，未来的路还很长很艰巨。晚上又看了许多鸡汤，下定决心自己要搞好ACM。

我有着自命不凡的骄傲，与ACM同样有着缘分。我要珍惜，今后不能随随便点想着放弃了。要加油呐！

窗外的夏天是咕噜咕噜的沸水，是瓜子壳和昏昏欲睡的旅人，是在阳光下飘扬的格子衬衫和风筝线，是车轮划过铁轨微微颤抖的声音和装在背包里的古老歌谣。

我要追上风，追上时间，拖着那些被偷走的限量版的夏天。

就算全都是假的，但我……是真的。

——疯狂阅读