Bài toán đặt trạm phát sóng (đề tuyển sinh PTNK)

[Duc_Khai_Tong (da sun kid)]

Đề: Cho dãy số sắp xếp tăng dần là tọa độ các điểm trên trục Ox. Tìm ra số trạm phát sóng ít nhất cần có để tất các địa điểm đều được phủ sóng.(trạm phát phải đặt trên các điểm đã cho)
Dòng đầu nhập n, r (r là bán kính phủ sóng của trạm phát).
Dòng tiếp theo nhập dãy n số.
VD:
INPUT
7 5
1 3 7 12 17 20 31
OUTPUT
3
Mọi người cho mình gợi ý về bài tập này với. Mình nghĩ mãi chỉ đc 1/2 số test nhưng chắc chắn đó không phải cách làm của bài này.

[SITUVN.gcd]

Đường kính = Bán kính * 2

[Duc_Khai_Tong (da sun kid)]

ý bạn là sao mình không hiểu. đề bài mình có vấn đề à.

[Duc_Khai_Tong (da sun kid)]

oke để mình tìm hiểu, cảm ơn bạn.

[hungaya (Hung)]

Mình nhầm, greedy algorithm, không phải là clustering.
Chạy từ k = 1 lên n, với k là số trạm, chạy tới khi k trạm phủ hết thì dừng.
Học statistics nhiều quá bị lạm dụng thuật ngữ.

k = 1:
Đặt tại 3 phủ được 1, 3, 7
Đặt tại 17 phủ được 12, 17, 20
Đặt tại 31 chỉ phủ được 31
… (tương tự cho 1, 7, 12, 20)

k = 2:
Đặt tại 3 và 17 phủ được 1, 3, 7, 12, 17, 20
Đặt tại 17 và 31 phủ được 12, 17, 20, 31
…

k = 3
Đặt tại 3, 17, 31 phủ hết 1, 3, 7, 12, 17, 20, 21
…

Vì vậy kết quả là 3

Độ phức tạp O(2ⁿ)

---

Cách phân cụm (clustering)

Chạy vòng for từ 1 tới 31 để phân từng nhóm

Nhóm 1:

• Tại 1, lấy 1 + 5 = 6
• Chạy tiếp for cho đến khi có phần tử > 6, được 7
• Lấy phần trước 7 là 3, 3 + 5 < 8
• Chạy tiếp for cho đến khi có phần tử > 8, được 12
• Lấy phần tử trước 12 là 7
• Nhóm 1 là các điểm { 1, 3, 7 }

Nhóm 2:

• 12 + 5 = 17
• Chạy for đến phần tử > 17, được 20
• Lấy phần tử trước 20 là 17
• 17 + 5 = 22
• Chạy for đến phần tử > 22, được 31
• Lấy phần tử trước 31 là 20
• Nhóm 2 là các điểm { 12, 17, 20 }

Nhóm 3:

• 31 + 5 = 36
• Chạy for đến phần tử > 36, kết thúc mảng vì 31 là phần tử cuối
• Nhóm 3 chỉ có 1 điểm { 31 }

Vì có 3 nhóm { 1, 3, 7 }, { 12, 17, 20 } và { 31 } nên kết quả là 3.

Độ phức tạp O(n)