欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2020牛客寒假算法基础集训营4 E 最小表达式(高精度+贪心)

程序员文章站 2022-06-02 20:25:04
...

题目链接
2020牛客寒假算法基础集训营4 E	最小表达式(高精度+贪心)
示例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;
}
相关标签: 高精度