Mã C ++ để đếm các nhóm tối đa có thể được tạo

Giả sử chúng ta có một mảng A với n phần tử. Có n nhóm học sinh. Nhóm là một người có thể viết mã với bất kỳ ai khác hoặc hai người muốn viết mã trong cùng một nhóm. Nhưng người cố vấn đã quyết định thành lập các đội gồm đúng ba người. Chúng ta phải tìm số đội tối đa gồm ba người mà người cố vấn có thể thành lập. Đối với nhóm hai người, cả hai sinh viên nên viết mã, hoặc cả hai không nên. Nếu hai sinh viên từ một nhóm hai người sẽ viết mã, thì họ phải ở trong cùng một nhóm.

Vì vậy, nếu đầu vào là A =[2, 2, 2, 1, 1, 1, 1], thì đầu ra sẽ là 3, vì người cố vấn có thể tạo các nhóm như:[Nhóm thứ nhất gồm hai người và nhóm thứ bảy của một người], [Nhóm thứ hai gồm hai người và nhóm thứ sáu gồm một người], [Nhóm thứ ba gồm hai người và nhóm thứ tư gồm một ngườ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 -

p := 0
q := 0
x := size of A
for initialize i := 0, when i < x, update (increase i by 1), do:
   a := A[i]
   if a is same as 1, then:
      p := p + 1
   Otherwise
      q := q + 1
if p > q, then:
   return q + (p - q)
otherwise when p < q, then:
   return p
Otherwise
   return p

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;
int solve(vector<int> A){
   int p = 0, q = 0;
   int x = A.size();
   for (int i = 0; i < x; i++){
      int a = A[i];
      if (a == 1){
         p = p + 1;
      }
      else{
         q = q + 1;
      }
   }
   if (p > q){
      return q + (p - q) / 3;
   }
   else if (p < q){
      return p;
   }
   else{
      return p;
   }
}
int main(){
   vector<int> A = { 2, 2, 2, 1, 1, 1, 1 };
   cout << solve(A) << endl;
}

Đầu vào

{ 2, 2, 2, 1, 1, 1, 1 }

Đầu ra

3