Mã C ++ để kiểm tra trò chơi đổ nước có tất cả người chiến thắng hay không

Giả sử chúng ta có một mảng A với n phần tử và có một số khác s. Có một cốc nước rỗng và n cốc nước không rỗng trên bàn. Trong một trò chơi, có rất ít người chơi. Trong mỗi nước đi, người chơi lấy một cốc nước không rỗng và đổ tất cả nước từ cốc đó vào cốc. Nếu nó đầy quá, người chơi sẽ bị thua. Chúng ta phải kiểm tra xem tất cả chúng sẽ là người chiến thắng hay không (chiếc cốc sẽ không quá đầy). Nếu một điểm đã được lấp đầy hoàn toàn, người chơi tiếp theo sẽ không chơi nước đi của mình. Đây là dung tích của cốc rỗng và A [i] là lượng nước có trong cốc thứ i.

Vì vậy, nếu đầu vào giống như A =[3, 1, 3]; s =4, thì kết quả đầu ra sẽ là True, vì bởi người chơi thứ nhất và thứ hai, chiếc cốc sẽ được lấp đầy. Đối với nước đi cuối cùng, người chơi sẽ không chơi nước đi đó.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

k := 0
n := size of A
sort the array A
for initialize i := 0, when i < n - 1, update (increase i by 1), do:
   k := k + A[i]
if k > s, then:
   return false
Otherwise
   return true

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A, int s){
   int k = 0;
   int n = A.size();
   sort(A.begin(), A.end());
   for (int i = 0; i < n - 1; i++)
      k += A[i];
   if (k > s)
      return false;
   else
      return true;
}
int main(){
   vector<int> A = { 3, 1, 3 };
   int s = 4;
   cout << solve(A, s) << endl;
}

Đầu vào

{ 3, 1, 3 }, 4

Đầu ra

1