Kiểm tra sắp xếp lại B để A[i]+B[i] ≤ x với mọi i bằng C++

Mô tả bài toán

Cho mảng A,B kích thước n và số x. Có thể sắp xếp lại B. Kiểm tra có thể làm sao cho A[i] + B[i] ≤ x ∀i.

Ví dụ

A=[1,2,3], B=[1,1,2], x=4 → Sắp B=[1,2,1] → 1+1≤4, 2+2≤4, 3+1≤4 → True.

Thuật toán

Sắp A tăng, B giảm (hoặc không sắp A, chỉ cần B giảm). Kiểm tra A[i] + B[n-1-i] ≤ x. Code: duyệt i, sum = A[i] + B[n-i-1], nếu bất kỳ sum > x thì false.

Code C++

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

bool solve(vector A, vector B, int x) {
    int n = A.size();
    sort(A.begin(), A.end());
    sort(B.begin(), B.end(), greater());
    for (int i = 0; i < n; i++) {
        if (A[i] + B[i] > x) return false;
    }
    return true;
}

int main() {
    vector A = {1,2,3};
    vector B = {1,1,2};
    int x = 4;
    cout << solve(A, B, x) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: {1,2,3}, {1,1,2}, 4

Output: 1 (true)