C++: Kiểm tra truy vấn tổng bằng 0

Bài toán: Mảng A chỉ chứa -1, 1. m truy vấn Q[i] = (l, r). Có thể sắp xếp lại A sao cho tổng đoạn [l,r] = 0? Trả về 1/0.

Quan sát: Tổng đoạn chẵn-length mới có thể = 0 (cần số -1 = số 1). Số cặp (-1,1) tối đa = min(count(-1), count(1)). Độ dài đoạn = len = r-l+1. Cần len chẵn và len/2 ≤ số cặp.

Code C++

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> A, vector<vector<int>> Q) {
    int n = A.size();
    int neg = 0;
    for (int x : A) if (x < 0) neg++;
    int pairs = min(neg, n - neg); // số cặp (-1,1) tối đa

    for (auto &q : Q) {
        int l = q[0], r = q[1];
        int len = r - l + 1;
        int ans = (len % 2 == 0 && len / 2 <= pairs) ? 1 : 0;
        cout << ans << ", ";
    }
}

int main() {
    vector<int> A = {-1, 1, 1, 1, -1};
    vector<vector<int>> Q = {{1,1}, {2,3}, {3,5}, {2,5}, {1,5}};
    solve(A, Q); // Output: 0, 1, 0, 1, 0
    return 0;
}

Kết quả

0, 1, 0, 1, 0