2020牛客寒假算法基础集训营4.E——最小表达式贪心 & 构造

实践是知识的母亲，知识是生活的明灯。这篇文章主要讲述2020牛客寒假算法基础集训营4.E——最小表达式贪心 & 构造相关的知识，希望能为你提供帮助。

??题目传送门??
题目描述
给出一个包含数字1-9和加号的字符串，请你将字符串中的字符任意排列，但每种字符数目不变，使得结果是一个合法的表达式，而且表达式的值最小。输出那个最小表达式的值
合法的表达式的定义如下：

一个数字，如233，是一个合法的表达式
A + B是合法的表达式，当且仅当 A , B 都是合法的表达式

保证给出的表达式经过重排，存在一个合法的解。
输入描述:
一行输入一个字符串，仅包含数字1-9和加号+。
字符串的长度小于
输出描述:
一行输出一个数字，代表最小的解。
输入

111+1
9998765432111
12+35
23984692+238752+2+34+

输出

【2020牛客寒假算法基础集训营4.E——最小表达式贪心 & 构造】22
1112345678999
38
5461

说明
11+11=22
25+13 = 38
emmm…第四组答案也是可以得到的
备注:
注意，答案长度可能长达500000个字符。
题解

题目还是很好想的，首先统计各种数字和加号的个数，这个毫无疑问。
考虑肯定位数越少，数值越小。那么我们知道
对于同样位数的数，肯定越大的数越低位越好。
首先第一想法是，我们可以贪心的构成所有的数字，然后把组成的各个数相加。
emmm，最开始没注意到答案范围，这样肯定是不行的，而且中间过程开longlong还自己重定义拓展了atoi函数
其实我们可以这样：
我们把拥有的数字降序排序，然后对应的，给每个数字一个权值，也就是它应该放的位置上的10的几次幂，这样线性复杂度就可以完成。
想法还是很简单的，细节看注释就好了

AC-Code

#include < bits/stdc++.h>
using namespace std;
#define
#define
const int maxn = 5e5 + 7;

int num[10]; // num[0]存加号数量
int ans[maxn];
int main()
ios;
string s; while (cin > > s)
for (int i = 0; i < s.length(); ++i)
++num[s[i] == + ? 0 : s[i] - 0];
int p = 1, cnt = 0; // cnt:[0,num[0]-1]
for (int i = 9; i > 0; --i)
while (num[i] > 0)
ans[p] += i;
--num[i];
cnt = (cnt + 1) % (num[0] + 1);
if (cnt == 0)++p;

for (int i = 1; i < maxn - 2; ++i)
ans[i + 1] += ans[i] / 10;
ans[i] %= 10;

bool flag = false;
for (int i = maxn - 1; i > 0; --i)
if (flag || ans[i])
cout < < ans[i];
flag = true;

cout < < endl;

return 0;