Chương trình C ++ để tìm số lượng nhóm có thể được hình thành từ tập hợp các lập trình viên

Giả sử chúng ta có một mảng A với n phần tử. A [i] thể hiện kỹ năng lập trình của sinh viên thứ i. Tất cả các phần tử trong A là phân biệt. Chúng tôi muốn chia họ thành các đội theo cách -

• Không có hai học sinh i và j sao cho | A [i] - A [j] | =1 người thuộc cùng một nhóm

• Số lượng đội là tối thiểu có thể.

Vì vậy, nếu đầu vào là A =[2, 3, 4, 99, 100], thì đầu ra sẽ là 2, bởi vì các nhóm là [2, 3, 4] và [99, 100]

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 -

dem := 1
sort the array A
for initialize i := 1, when i < size of A, update (increase i by 1), do:
   if A[i] - A[i - 1] is same as 1, then:
      dem := 2
   return dem

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 dem = 1;
   sort(A.begin(), A.end());
   for (int i = 1; i < A.size(); i++)
      if (A[i] - A[i - 1] == 1)
         dem = 2;
   return dem;
}
int main() {
   vector<int> A = { 2, 3, 4, 99, 100 };
   cout << solve(A) << endl;
}

Đầu vào

{ 2, 3, 4, 99, 100 }

Đầu ra

2