Giả sử chúng ta có một mảng A với n phần tử và một số k. Có n sinh viên trong một lớp. Đánh giá của sinh viên thứ i là A[i]. Chúng ta phải hình thành một đội với k sinh viên sao cho đánh giá của tất cả các thành viên đội đều khác nhau. Nếu không thể trả về "Impossible", ngược lại trả về dãy chỉ số.
Ví dụ, 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 bài toán này, chúng ta sẽ làm theo các bước sau:
Định nghĩa hai mảng lớn app và ans và điền cnt := 0 n := kích thước của A for khởi tạo i := 1, khi i <= n, cập nhật (tăng i lên 1), do: a := A[i - 1] if app[a] bằng 0, thì: (tăng app[a] lên 1) tăng cnt lên 1; ans[cnt] := i if cnt >= k, thì: for khởi tạo i := 1, khi i <= k, cập nhật (tăng i lên 1), do: in ans[i] Ngược lại return "Impossible"
Ví dụ
Xem 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,