2020牛客寒假算法基础集训营4 E：最小表达式

E:最小表达式

考察点 : 贪心，高精度

坑点  :  高精度一定不要写错,一定一定不要写错

         剩下的就是细节问题

侃侃：

1、字符串长度达到 5e5,如果要涉及到加法,乘法,普通的肯定会爆 long long的,那么就需要用到

   高精度了。

2、怎么贪呢 ?

   一个数怎么样会最小呢？只有最高位最小,然后次高位较小,这是这个数就应该会最小(可以自己模拟一下)

   另外,这个字符串中的所有 '+' 我们肯定都会用到,因为只有这样所得到的和才会更小,所以如果 ‘+’ 有

   ans 个,那么我们就可以将所有整个字符串分成 ans + 1 份。

   接下来将所有字符进行排序(从小到大),然后平均分配到每一份中,最后用高精度进行 累加即可(刚开始我还

   想着先 * 10 + 某个字符,实际上根本不用,因为我们的每一份就是一个整数,而在大数相加的时候也是字符串

   所以直接相加即可)

3、注意高精度一定不要写错,否则真的过不了

Code:

#include <vector>

#include <cstdio>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 5 * 1e5 + 100;

typedef long long LL;

char str[maxn];

int a[maxn];

vector<int>ve[maxn];

vector<int>res;

vector<int> add(vector<int> &A,vector<int> &B) {

    if(A.size() < B.size()) return add(B,A);         // 尽量用长的 + 短的,因为这样多余的部分我们就可以直接进行处理了

    vector<int> C;                                   // 设置一个 vector 类型的变量,用来作为返回的值

    int t = 0;

    for(int i = 0; i < A.size(); i ++) {

        t += A[i];

        if(B.size() > i) t += B[i];              // B 有一定的限制,不能一直加 呀

        C.push_back(t % 10);

        t /= 10;                                 // 进位

    }

    if(t) C.push_back(t);                            // 可能会多出来一个,例如3位数 + 3 位数 ,结果有可能是 4 位数

    return C;

}

int main(void) {

	int ans = 0,len;

	bool vis = false;

	scanf("%s",str + 1);

	len = strlen(str + 1);

	int a_num = 1;

	for(int i = 1; i <= len; i ++) {

		if(str[i] == '+') {

			ans ++;     // '+' 的次数

		} else {

			a[a_num ++] = str[i] - '0';

		}

	}

	if(ans != 0)

		ans ++;            // 份数应该 + 1

	sort(a + 1,a + a_num);

	if(ans == 0) {

		for(int i = 1; i <= len; i ++) {

			cout << a[i];

		}

		cout << endl;

	} else {

		int pos = 0;

		for(int i = 1; i <= a_num - 1; i ++) {

			if(i % ans == 0) {

				pos ++;

				ve[pos].push_back(a[i]);

				pos = 0;

				continue;

			}

			pos ++;

			ve[pos].push_back(a[i]);

		}

		for(int i = 1; i <= ans; i ++) {

                        // 取反,便于下面进行计算

			reverse(ve[i].begin(),ve[i].end());

			res = add(res,ve[i]);

		}

		for(int i = res.size() - 1; i >= 0; i --) {

			cout << res[i];

		}

		cout << endl;

	}

	return 0;

}

巴特西

2020牛客寒假算法基础集训营4 E：最小表达式

E:最小表达式

侃侃：

Code:

最新文章

热门文章

巴特西

2020牛客寒假算法基础集训营4 E：最小表达式

E:最小表达式

侃侃 ：

Code:

最新文章

热门文章

侃侃：