题解 | #字母统计#

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

Main idea:
设两个子数组的元素和分别为 sum1, sum2，数组的元素和为sum，则：
sum=sum1+sum2
sum1-sum2=sum-2*sum2>=0, s.t. sum1>=sum2
sum2<= (sum/2)
因此问题转化为找一个子数组使得其和接近于 sum/2 且 小于等于 sum/2。
*/

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <bitset>
#include <algorithm>
#include <limits>
#include <functional>


using namespace std;

int result = 0;
int arrlen = 0;
int arrsum = 0;
int target = 0;
vector<int> arr;


bool cmp(int x, int y) {
    return x > y;
}


void dfs(int sum, int index) {
    //if (index >= arrlen || sum + (arrlen - index) * arr[index] < target)
    if (index >= arrlen)
        return;        // pruning, when we add all the rest data sum and it's smaller than the target, we can just return. This means 'result' can't be further improved by the following codes. 
    if (sum + arr[index] <= target) {
        result = max(sum + arr[index], result);
        if (result == target) return;
        dfs(sum + arr[index], index + 1);        // add the number to the backpack if the current add can't violate the condition
    }
    dfs(sum, index + 1);        // not add the number to the backpack
}


bool sto_vec(const string& str, vector<int>& vec) {//把数组分离出来
    int count = 0;
    for (int i(0); i < str.size(); ++i) {
        if (str[i] >= '0' && str[i] <= '9')
            count++;
        else if (str[i] == ' ' && count != 0) {
            vec.push_back(stoi(str.substr(i - count, count)));
            count = 0;
        }
        else
            return false;

    }
    if (count > 0)
        vec.push_back(stoi(str.substr(str.size() - count, count)));
    return true;
}


void method_2() {
    int num = 0;
    string tmp;
    bool flag = true;
    while (true) {
        arr.clear();
        while (true) {
            if (cin >> num) {
                arr.push_back(num);
            }
            else {
                cin.clear();
                cin.sync();
                while (cin.get() != '\n') {
                    continue;        // clear the input area
                }
                cout << "ERROR" << endl;
                flag = false;
                break;
            }
            if (cin.get() == '\n')
                break;
        }
        if (flag == false) {
            flag = true;
            continue;
        }
        arrlen = arr.size();
        arrsum = accumulate(arr.begin(), arr.end(), 0);
        target = ceil(arrsum / 2);

        // sort the array, benifit for pruning
        sort(arr.begin(), arr.end());
        dfs(0, 0);
        cout << result << " " << arrsum - result << endl;
    }
}


int main() {
    // method 1
    int num = 0;
    string tmp;
    while (getline(cin, tmp) && !tmp.empty()) {
        arr.clear();
        result = 0;
        if (!sto_vec(tmp, arr)) {
            cout << "ERROR" << endl;
            continue;
        }
        arrlen = arr.size();
        arrsum = accumulate(arr.begin(), arr.end(), 0);
        target = ceil(arrsum / 2);

        //sort the array, benifit for pruning
        sort(arr.begin(), arr.end(),cmp);
        dfs(0, 0);
        cout << arrsum - result << " " << result << endl;
    }
    // method 2
    //method_2();
    return 0;
}