# Search : Count Place

Tuyến phố thông minh của nhà anh Việt có nhiều tòa nhà, tòa nhà thứ i có khoảng cách x[i] mét so với đầu của tuyến phố. Vì anh Việt là người giàu có và khá thoải mái chuyện tiền bạc nên anh đã quyết định sẽ đặt các trạm phát sóng wifi miễn phí tại các tòa nhà dọc theo tuyến phố thông minh của nhà anh. Mỗi thiết bị phát wifi có thể phủ sóng trong phạm vi k mét, tức là các tòa nhà có khoảng cách đến thiết bị không vượt quá k mét thì sẽ sử dụng được wifi từ thiết bị này.

Bạn hãy viết chương trình giúp anh Việt Ducky tìm cách đặt các trạm wifi để số lượng trạm wifi là ít nhất và tất cả các tòa nhà đều có thể sử dụng wifi.

Ví dụ:

• Với a = [1, 2, 3, 4, 5] , k = 1 thì đầu ra của chương trình countPlace(a, k) = 2
  Việt sẽ đặt wifi ở tòa nhà có khoảng cách là 2 (tòa nhà có khoảng cách là 1 và 3 cũng sẽ bắt được sóng) và tòa nhà có khoảng cách là 4 (tòa nhà có khoảng cách là 5 sẽ bắt được sóng)
  
• Với a = [1, 3, 4, 7, 8, 10], k = 2 thì đầu ra của chương trình countPlace(a, k) = 2
  Việt sẽ đặt wifi ở tòa nhà có khoảng cách là 3 (tòa nhà có khoảng cách là 1 và 4 cũng sẽ bắt được sóng) và tòa nhà có khoảng cách là 8 (tòa nhà có khoảng cách là 7 và 10 sẽ bắt được sóng)

Đầu vào/Đầu ra:

• [Thời gian chạy] 1 giây
  
• [Đầu vào] Array.integer a
  Mảng số nguyên dương a tăng dần
  0 < a.length <= 1000

• [Đầu vào] Integer k
  0 < k <=1000

• [Đầu ra] Integer

Hướng dẫn bài tập.

Code mẫu:

Ngôn ngữ Java:

static int countPlace(int[] a, int k)
{
	int count =0;
	int i = 0;
	while(i < a.length){
		int ht = i;
		if(ht == a.length -1) {
			count++;
			break;
		}
		int vt = i+1;
		while( vt < a.length&&a[vt]- a[ht] <= k){
			vt++;
		}
		if(vt < a.length) {
			i = vt - 1;
			int j = i + 1;
			while(j < a.length&&a[j] - a[i] <= k ){
				j++;
			}
			i = j;
			count++;
		}else {
			count++;
			break;
		}
	}
	return count;
}