C++: Kiểm tra trò chơi đổ nước có ai thua không

Bài toán: n ly nước lượng A[i], 1 ly rỗng dung tích s. Người chơi lần lượt đổ toàn bộ 1 ly vào ly rỗng. Nếu tràn → thua. Nếu ly rỗng đã đầy, người sau không chơi. Kiểm tra có ai thua không.

Giải pháp: Sắp xếp A tăng. Cộng dồn n-1 ly nhỏ nhất. Nếu tổng ≤ s → không ai thua (True).

Code C++

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

bool solve(vector<int> A, int s) {
    sort(A.begin(), A.end());
    int sum = 0;
    for (int i = 0; i < (int)A.size() - 1; i++)
        sum += A[i];
    return sum <= s;
}

int main() {
    vector<int> A = {3, 1, 3};
    int s = 4;
    cout << solve(A, s) << endl; // 1 (true)
    return 0;
}

Kết quả

1

Giải thích: Sắp xếp → [1,3,3]. 2 ly đầu sum=4 ≤ s=4. Ly cuối không được chơi.