Chương trình C ++ để tìm chuỗi chỉ số của các thành viên trong nhóm

Giả sử chúng ta có một mảng A với n phần tử và một số k. Có n học sinh trong một lớp. Xếp loại của sinh viên thứ i là A [i]. Chúng ta phải thành lập một đội với k học sinh sao cho xếp hạng của tất cả các thành viên trong nhóm là khác biệt. Nếu không thể, hãy trả về "Không thể", nếu không, hãy trả về chuỗi chỉ số.

Vì vậy, nếu đầu vào là A =[15, 13, 15, 15, 12]; k =3, thì đầu ra sẽ là [1, 2, 5].

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 -

Define two large arrays app and ans and fill them with
cnt := 0
n := size of A
   for initialize i := 1, when i <= n, update (increase i by 1), do:
      a := A[i - 1]
      if app[a] is zero, then:
         (increase app[a] by 1)
         increase cnt by 1;
         ans[cnt] := i
if cnt >= k, then:
   for initialize i := 1, when i <= k, update (increase i by 1), do:
      print ans[i]
Otherwise
   return "Impossible"

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;

void solve(vector<int> A, int k) {
   int app[101] = { 0 }, ans[101] = { 0 }, cnt = 0;
   int n = A.size();
   for (int i = 1; i <= n; i++) {
      int a = A[i - 1];
      if (!app[a]) {
         app[a]++;
         ans[++cnt] = i;
      }
   }
   if (cnt >= k) {
      for (int i = 1; i <= k; i++)
         cout << ans[i] << ", ";
   }
   else
      cout << "Impossible";
}
int main() {
   vector<int> A = { 15, 13, 15, 15, 12 };
   int k = 3;
   solve(A, k);
}

Đầu vào

{ 15, 13, 15, 15, 12 }, 3

Đầu ra

1, 2, 5,