首页 > 代码库 > NYOJ 1233 差值(字符串排序+大数减法)
NYOJ 1233 差值(字符串排序+大数减法)
题意
T组测试数据,每组数据给你n(0<n<=1000)个无符号整型范围内的数,把这些数字任意排列后连接成一个大数,求能排出的所有数当中最大的与最小的两个数的差值。
例如{1, 2}, 最大为21,最小为12,差值为9。
样例输入
1
3
1 2 3
样例输出
198
思路
乍一看是个大数问题,然而后来发现排序才是这道题的重点。
一开始想的是按数字的大小排序,但显然不对。例如{9, 10},按数字排序的话9 < 10,则最小值为910,但是显然109更小。
后来想到按字典序排,并且深信不疑的WA了两次(0﹏0)
例如{9, 90},按字典序排的话是9 < 90,则最小值为990,但显然909更小。
最后才想到要把两个字符串拼接以后再按字典序排。例如{567, 5674}就比较5675674和5674567哪个更小,显然后者小,所以排序后的结果应为{5674, 567}。
用C++的string的话可以很优美的实现这个比较函数。
bool cmp(const string a, const string b){ return (a+b) < (b+a);}
然而不知道是C++的读入太慢还是string慢,居然超时了(⊙_⊙)
然后加上一句取消cin与stdin同步以后就险过了~~~2644ms(时限3000ms)
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <string> 5 using namespace std; 6 const int N = 1e3+10; 7 string str[N], sMax, sMin; 8 bool cmp(const string a, const string b){ 9 return (a+b) < (b+a);10 }11 void Subtract(void)12 {13 int len = sMax.length();14 for(int i=len-1; i; --i)15 {16 if(sMax[i] >= sMin[i])17 sMax[i] -= sMin[i] - ‘0‘;18 else19 sMax[i] -= sMin[i] - 10 - ‘0‘, --sMax[i-1];20 }21 sMax[0] -= sMin[0] - ‘0‘;22 int i;23 for(i=0; i<len && sMax[i] == ‘0‘; ++i);24 if(i == len)25 cout << 0 << endl;26 else27 {28 for(; i<len; ++i)29 cout << sMax[i];30 cout << endl;31 }32 }33 int main(void)34 {35 std::ios::sync_with_stdio(false);36 int kase, n;37 cin >> kase;38 while(kase--)39 {40 cin >> n;41 for(int i=0; i<n; ++i)42 cin >> str[i];43 sort(str, str+n, cmp);44 sMax = sMin = "";45 for(int i=0; i<n; ++i)46 sMin += str[i];47 for(int i=n-1; i>=0; --i)48 sMax += str[i];49 Subtract();50 }51 }
NYOJ 1233 差值(字符串排序+大数减法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。