Số đoạn thẳng tối đa chứa các điểm cho trước trong C++

Nhiệm vụ: tìm số đoạn thẳng tối đa có thể chứa các điểm cho trước.

Cho mảng a1[] kích thước n1 và hai số nguyên A, B. Từ a1[] tạo n1 đoạn thẳng với đầu/mút: a1[i] - A và a1[i] + B.

Mảng a2[] kích thước n2 chứa các điểm. Gán điểm vào đoạn thẳng sao cho số đoạn có điểm là tối đa. Mỗi điểm chỉ gán cho một đoạn.

Ví dụ 1

Đầu vào** –

a1[] = {1, 4, 5}, a2[] = {2, 8}, A = 1, B = 2

Đầu ra** – 1

Giải thích** – Đoạn thẳng: (0,3), (3,6), (4,7). Điểm 2 gán cho đoạn (0,3). Điểm 8 không gán được đoạn nào. Kết quả = 1.

Ví dụ 2

Đầu vào** –

a1[] = {1, 2, 3, 4, 6, 7}, a2[] = {2, 5, 6, 8}, A = 0, B = 1

Đầu ra** – 4

Phương pháp (Tham lam + Sắp xếp)

Sắp xếp cả hai mảng a1 và a2.

Duyệt đoạn thẳng theo thứ tự, với mỗi đoạn tìm điểm đầu tiên trong a2 nằm trong đoạn.

Dùng con trỏ j duyệt a2: nếu điểm < đầu đoạn → bỏ qua (j++); nếu điểm > cuối đoạn → đoạn này không gán được (break); nếu trong đoạn → gán, ans++, j++, break.

Ví dụ

#include <bits/stdc++.h> using namespace std; int Max(vector<int> a1, vector<int> a2, int n1, int n2, int A, int B) { sort(a1.begin(), a1.end()); sort(a2.begin(), a2.end()); int j = 0, ans = 0; for (int i = 0; i < n1; i++) { while (j < n2) { if (a1[i] + B < a2[j]) break; if (a2[j] >= a1[i] - A && a2[j] <= a1[i] + B) { ans++; j++; break; } else j++; } } return ans; } int main() { int A = 0, B = 1; vector<int> a1 = { 1, 2, 3, 4, 6, 7 }; int n1 = a1.size(); vector<int> a2 = { 2, 5, 6, 8 }; int n2 = a2.size(); cout << Max(a1, a2, n1, n2, A, B); return 0; }

Đầu ra

4