题解 | 喜欢切数组的红

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool havePositive(vector<int>& positive, int left, int right) {
    if (positive[right] - positive[left] > 0)
        return true;
    return false;
}

int main() {
    int a;
    cin >> a;
    vector<int> nums(a, 0);

    vector<int> positive(a + 1, 0);
    int sum = 0;
    // cout << positive[0] <<endl;
    for (int i = 0; i < a; i++) {
        cin >> nums[i];
        sum += nums[i];
        positive[i + 1] = (nums[i] > 0) ? positive[i] + 1 : positive[i];
        // cout << positive[i] << " " << positive[i + 1] << " "  << nums[i] <<endl;
    }
    if (sum % 3) {
        cout << 0 << endl;
        return 0;
    }

    int target = sum / 3;

    vector<int> split1, split2;
    int preSum = 0;
    for (int i = 0; i < nums.size(); i++) {
        preSum += nums[i];
        if (preSum == target && havePositive(positive, 0, i + 1)) {
            split1.push_back(i + 1);
        } else if (preSum == 2 * target && havePositive(positive, i + 1, nums.size())) {
            split2.push_back(i + 1);
        }
    }
    int res = 0;

    for (auto& s1 : split1) {
        for (auto& s2 : split2) {
            // cout << s1 << " " << s2 <<endl;
            if (s1 < s2) {
                if (havePositive(positive, s1, s2))
                    res ++;
            }
        }
    }
    cout << res << endl;

}
// 64 位输出请用 printf("%lld")