首页 > 代码库 > NYOJ 1233 差值(字符串排序+大数减法)

NYOJ 1233 差值(字符串排序+大数减法)

2024-08-13 06:04:11   220人阅读

题意
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 差值(字符串排序+大数减法)


联系
我们