2020牛客寒假算法基础集训营4 E 最小表达式(高精度+贪心)
程序员文章站
2022-06-02 20:25:04
...
题目链接
示例1
输入
111+1
复制
22
11+11=22
示例2
输入
9998765432111
输出
1112345678999
示例3
输入
12+35
输出
38
25+13 = 38
示例4
输入
23984692+238752+2+34+
输出
5461
备注:
注意,答案长度可能长达500000个字符。
思路:贪心思想,小的尽量放前,大的放后,如果有n个加号的话尽量平均分,注意高精度。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
string str,ans[maxn];
string add(string a, string b) {
string c;
int lena = a.length();
int lenb = b.length();
int up = 0;
int i, j;
for (i = lena - 1, j = lenb - 1; i >= 0 && j >= 0; i--, j--) {
int num = a[i] - '0' + b[j] - '0';
num += up;
c += (num % 10 + '0');
up = num / 10;
}
for (; i >= 0; i--) {
int num = a[i] - '0';
num += up;
c += (num % 10 + '0');
up = num / 10;
}
while (up) {
int num = up % 10;
c += (num % 10 + '0');
up /= 10;
}
reverse(c.begin(), c.end());
return c;
}
int main()
{
int cnt=0,id=-1;
cin>>str;
sort(str.begin(),str.end());
for(int i=0;i<str.size();++i)
if(str[i]=='+') cnt++;
else if(id==-1) id=i;
cnt++;
for(int i=id,k=0;i<str.size();++k,++i)
ans[k%cnt]+=str[i];
string res=ans[0];
for(int i=1;i<cnt;++i) res=add(res,ans[i]);
cout<<res<<endl;
}
下一篇: 思考题(精度问题)