CTDL và giải thuật - Bài tập hay về sắp sếp

Trong diễn biến dịch Covid-19 đang diễn ra khá phức tạp, việc tuyền truyền cách phòng tránh dịch là rất quan trong, gọi a[i] là tọa độ của người thứ i, khoảng cách giữa hai người i và j là |a[i]-a[j]|. Một người có thể truyền được thông tin đến người khác nếu khoảng cách giữa họ không vượt quá k.

Để tuyền truyền thông tin nhanh chóng thì người ta sẽ chỉ truyền thông tin cho 1 số người ban đầu, sau đó họ sẽ truyền thông tin cho người khác, Hãy đưa ra số lượng ít nhất là số người ban đầu cần truyền thông tin, để sao cho tất cả mọi người đều tiếp cận được thông tin.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    6
    1 3 2 5 10 8
    2

    2

    Với a = [1, 3, 2, 5, 10, 8] và k = 2, thì kết quả mong muốn là 2.
    Giải thích: Chỉ cần truyền thông tin cho  a[0] và a[4].
     
  • Test mẫu 2:
     
    Input Output

    4
    7 5 8 9
    3

    1

    Với  a = [7, 5, 8, 9] và  k = 3, thì kết quả mong muốn là 1.

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

  • [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.

  • [Đầu vào] Array: Integer: a.
    1 ≤ a.size()≤ 105.
    0 ≤ a[i] ≤ 109

  • [Đầu vào]: Integer: k.
    1 ≤ k ≤ 105.

  • [Đầu ra] Integer.
    Số lượng người ban đầu cần truyền thông tin.

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

Ý tưởng:

Sắp xếp dãy thành dãy không giảm, do kích thước mảng rất lớn nên bạn chỉ nên áp dụng mergeSort hoặc quickSort.

Dùng biến count để đếm những vị trí i (1 ≤ i < a.size) mà a[i] - a[i-1] > k. Kết quả chính là count + 1.

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

void quickSort(int a[], int l, int r){
	int p = a[(l+r)/2];
	int i = l, j = r;
	while (i < j){
		while (a[i] < p){
			i++;
		}
		while (a[j] > p){
			j--;
		}
		if (i <= j){
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i++;
			j--;
		}
	}
	if (i < r){
		quickSort(a, i, r);
	}
	if (l < j){
		quickSort(a, l, j);
	}
}
int result(int a[], int n, int k){
	int count = 0;
	for (int i = 1; i < n; i++){
		if (a[i] - a[i-1] > k){
			count ++;
		}
	}
	return count + 1;	
}
int a[100001];
int main()
{
	int n, k;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];		
	}
	cin >> k;
	quickSort(a, 0, n-1);
	cout << result(a, n, k);
    return 0;
}