1799 Problem  A 第二题

问题 A: 第二题

时间限制: 1 Sec  内存限制: 32 MB
提交: 83  解决: 0
[提交][状态][讨论版][命题人:外部导入]

题目描述

一个数组中有若干正整数，将此数组划分为两个子数组，使得两个子数组各元素之和a,b的差最小，对于非法输入应该输出ERROR。

输入

数组中的元素

输出

降序输出两个子数组的元素和

样例输入

10 20 30 10 10
10 20 abc 10 10

样例输出

40 40
ERROR

//测试可过but未AC,运行错误数组越界？
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
long long a[400000], dp[400000];
//思路:将数组求和得sum，分出一个数组使其接近sum/2，本质为01背包
//即从1-n物品中选取若干个，其重量不超过sum/2,且重量达最大
//dp[j]即在重量不超过j时所能达到的最大值
int main() {
string s;
while (getline(cin, s)) {
long long n = 1, sum = 0;
bool flag = false;
memset(a, 0, sizeof(a));
memset(dp, 0, sizeof(dp));
for (int i = 0; i < s.length(); i++) {
if (s[i] >= '0'&&s[i] <= '9') {
a[n] *= 10;
a[n] += s[i] - '0';
}
else if (s[i] == ' ') {
sum += a[n];
n++;
}
else {
flag = true;
break;
}
}
sum += a[n];
if (flag || n == 1) {
cout << "ERROR" << endl;
continue;
}
for (int i = 1; i <= n; i++) {
for (int j = sum / 2; j >= a[i]; j--) {
dp[j] = max(dp[j], dp[j - a[i]] + a[i]);
}
}
cout << sum - dp[sum / 2] << " " << dp[sum / 2] << endl;
}
return 0;
}

最后

以上就是玩命皮卡丘为你收集整理的1799 Problem  A 第二题的全部内容，希望文章能够帮你解决1799 Problem  A 第二题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。