Bài 4:
Trước hết sắp xếp dãy vào tăng dần. Sau đó đi từ trái sang phải (nhỏ đến lớn), tìm phần tử xa nhất tiếp theo mà đặt trạm tại đó nó vẫn có thể phủ kín tiếp đc hết về phía trái. mỗi lần tìm đc thì ghi lại vị trí và tăng số đếm cho các trạm lên 1. Sau khi đi hết dãy thì ta đc kết quả.
Lấy ví dụ như đầu vào trong đề: sắp xếp lại tăng dần ta đc dãy: 0, 1, 3, 5, 6, 9, 10, 11. Từ trái sang phải ta thấy vị trí xa nhất mà vẫn phủ đc hết phía trái là 1, vì đặt trạm tại 1 với bán kính 2 thì ta vẫn phủ đc hết phía bên trái, còn đặt trạm tại 3 thì ko phủ đc hết bên trái. như vậy vị trí 1 là 1 vị trí cần tìm. Khi đặt trạm tại 1 thì vị trí tọa độ trái cần phủ đc sẽ tăng lên 1 + 2 + 1 = 4. Xét các giá trị tiếp theo xem tọa độ nào xa nhất mà phủ đc vị trí 4, đó là tọa độ 6, vì nếu đặt sang tọa độ 9 thì ko thể phủ tới vị trí 4 đc. Vậy ghi lại vị trí 6 và làm tiếp. lúc này tọa độ trái sẽ chuyển sang vị trí 6 + 2 + 1 = 9. Tiếp theo vị trí nào xa nhất trong dãy mà có thể phủ tới vị trí 9, đó là 11, cũng là tọa độ cuối cùng trong dãy. Ghi lại tọa độ 11 này. Số lượng trạm tổng cộng đc đếm là 3.
Input: n, R và dãy vào a1, a2, ...., am
Output: k - số trạm ít nhất cần xây, và các vị trí đặt trạm theo dãy trên.
// k = 0;
// b = dãy a.
// sắp xếp b tăng dần.
// có thể khai báo mảng logic c (bool) để ghi lại vị trí trong mảng a. cỡ của c và a = nhau.
// khởi tạo tọa độ phủ kín phía trái = 0 (vì trạm đầu tiên tọa độ 0), tdt = 0;
// biến logic check = true; // kiểm tra xem có xây được các trạm để phủ kín ko.
for i = 1 to m:
{
// kiểm tra i có là vị trí xa nhất trong b sao cho vẫn phủ kín đc phía trái hay ko:
if ((b(i) - R) <= tdt)
{
if (i < m)
{
if ((b[i+1] - R) > tdt)
{
k = k + 1; // tăng biến đếm thêm 1
// Ghi lại vị trí trạm là vị trí có tọa độ b, bằng cách tìm trong dãy a vị trí nào có giá trị = b, rồi gán c tại vị trí đó = true:
for j = 1 to m do
if (a[j] == b(i)) then c[j] = true;
// thay đổi lại vị trí của tọa độ trái:
tdt = b(i) + R + 1; // vị trí mới lúc này là vị trí xa nhất bên trái tiếp theo.
}
}
else
{
// duyệt đến tọa độ cuối trong dãy b.
if (tdt < n-1) // tức là chưa phủ hết.
{
// Lại làm jống trên:
k = k + 1; // tăng biến đếm thêm 1
// Ghi lại vị trí trạm là vị trí có tọa độ b, bằng cách tìm trong dãy a vị trí nào có giá trị = b, rồi gán c tại vị trí đó = true:
for j = 1 to m do
if (a[j] == b(i)) then c[j] = true;
// thay đổi lại vị trí của tọa độ trái:
tdt = b(i) + R + 1; // vị trí mới lúc này là vị trí xa nhất bên trái tiếp theo.
}
// Kiểm tra có phủ hết dãy nữa hay ko:
if (tdt < n-1) check = false;
}
}
else check = false;
}
// if (check) then Ghi ra file số k và các vị trí có giá trị true trong mảng c.
else In ra là ko thể có cách nào phủ kín đc.
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
