สมมติว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบ และตัวเลข k มีนักเรียน n คนในชั้น คะแนน (rating) ของนักเรียนคนที่ i คือ A[i] เราต้องจัดทีม k คน โดยที่คะแนนของสมาชิกทุกคนต้องแตกต่างกัน หากทำไม่ได้ ให้คืนค่า "Impossible" มิฉะนั้นคืนค่าลำดับดัชนี
เช่น ถ้าค่าที่ป้อนเข้าเป็น A = [15, 13, 15, 15, 12]; k = 3 ผลลัพธ์จะได้ [1, 2, 5]
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
กำหนดอาร์เรย์ใหญ่ 2 ตัว app และ ans เติมด้วย cnt := 0 n := ขนาดของ A สำหรับ i := 1 เมื่อ i <= n เพิ่ม i ทีละ 1 ทำ: a := A[i - 1] ถ้า app[a] เป็นศูนย์ แล้ว: (เพิ่ม app[a] ขึ้น 1) เพิ่ม cnt ขึ้น 1; ans[cnt] := i ถ้า cnt >= k แล้ว: สำหรับ i := 1 เมื่อ i <= k เพิ่ม i ทีละ 1 ทำ: พิมพ์ ans[i] มิฉะนั้น คืนค่า "Impossible"
ตัวอย่างโค้ด
ดูการนำไปใช้จริงด้านล่างเพื่อความเข้าใจที่ดียิ่งขึ้น:
#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); }
ข้อมูลนำเข้า
{ 15, 13, 15, 15, 12 }, 3
ข้อมูลส่งออก
1, 2, 5,
