题解 | 第二题

// 第一反应动态规划 但是dp数组太大MLE
// 考虑dfs+减枝
#include <bits/stdc++.h>
using namespace std;
string s;
long long sum, half, bigAns; // bigAns为超过half的最小值
vector<int> nums; // 输入数组
vector<int> back_sum; // 后缀和数组

// 处理输入
bool toNums(){
    int n = s.length(), num = 0;
    bool flag = true;
    for(int i = 0; i < n; i++){
        if(s[i] == ' '){
            if(num == 0) continue;
            nums.push_back(num);
            sum += num;
            num = 0;
        }else if(s[i] >= '0' && s[i] <= '9'){
            num = num * 10 + s[i] - '0';
            if(i + 1 == n){
                nums.push_back(num);
                sum += num;
            }
        }else{
            flag = false;
            break;
        }
    }
    return flag;
}

// dfs + 减枝
void dfs(int index, long long now_sum){
    if(now_sum >= half){
        bigAns = min(bigAns, now_sum);
        return;
    }
    if(index >= nums.size()) return;
    if(now_sum >= bigAns) return;
    if(now_sum + back_sum[index] < half) return; // 当前和加上后续所有元素均小于half
    dfs(index + 1, now_sum + nums[index]);
    dfs(index + 1, now_sum);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    while(getline(cin, s)){
        sum = 0;
        nums.clear();
        if(!toNums()){
            cout << "ERROR" << '\n';
            continue;
        }
        //直接dfs会TLE 先把数组从大到小排序
        sort(nums.begin(), nums.end());
        reverse(nums.begin(), nums.end());
        back_sum.clear();
        back_sum.resize(nums.size() + 1, 0);
        half = sum / 2;
        bigAns = LLONG_MAX;
        for(int i = nums.size() - 1; i >= 0; i--){
            back_sum[i] = back_sum[i + 1] + nums[i];
        }
        dfs(0, 0);
        // 当sum为奇数时 half向下取整 bigAns不一定大
        bigAns = max(bigAns, sum - bigAns);
        cout << bigAns << ' ' << sum - bigAns << '\n';
    }

    return 0;
}