Kiểm tra trạng thái đống đá ngày thứ hai có hợp lệ bằng C++

Mô tả bài toán

Cho hai mảng X và Y cùng kích thước. X[i] là số đá trong đống i ngày 1, Y[i] là số đá ngày 2. Trong ngày 1, mọi người có thể thêm đá vào đống hoặc chuyển đá giữa các đống (không bị lấy đi). Kiểm tra xem Y có thể đạt được từ X không (tức tổng đá không giảm).

Ví dụ

X = [1,2,3,4,5], Y = [2,1,4,3,5] → Hợp lệ (true). Vì có thể chuyển 1 đá từ đống 2 sang 1, và 1 đá từ đống 4 sang 3.

Thuật toán

Chỉ cần kiểm tra tổng Y <= tổng X. Nếu tổng Y > tổng X thì không thể (vì không thêm đá mới).

Code C++

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

bool solve(vector<int> A, vector<int> B) {
    int n = A.size();
    long long sumA = 0, sumB = 0;
    for (int i = 0; i < n; i++) sumA += A[i];
    for (int i = 0; i < n; i++) sumB += B[i];
    return sumB <= sumA;
}

int main() {
    vector<int> X = {1,2,3,4,5};
    vector<int> Y = {2,1,4,3,5};
    cout << solve(X, Y) << endl;
    return 0;
}

Đầu vào / Đầu ra

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

Output: 1 (true)