HSG THPT Bà Rịa - Vũng Tàu 2025 - Lắp ráp thiết bị

Xem dưới dạng PDF

Gửi bài giải

Điểm: 20
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M

Tác giả:
Kiểu bài tập

Công ty Alpha có \(k\) thiết bị điện tử được đánh số từ \(1\) đến \(k\), để hoạt động ổn định, thiết bị thứ \(i\) cần bộ nguồn có công suất theo lý thuyết là \(t_i\). Thực tế, Công ty có sẵn \(n\) bộ nguồn được đánh số từ \(1\) đến \(n\), bộ nguồn thứ \(j\) \((1 \le j \le n)\) có công suất là \(p_j\). Nếu bộ nguồn thứ \(j\) gắn vào thiết bị thứ \(i\) thì giá trị \(|p_j - t_i|\) được gọi là độ gây hại của thiết bị này, giá trị này càng nhỏ thì độ ổn định của thiết bị càng cao. Để \(k\) thiết bị này hoạt động tốt nhất có thể, công ty yêu cầu nhân viên kỹ thuật phải chọn ra \(k\) trong \(n\) bộ nguồn có sẵn sao cho tổng độ gây hại cho \(k\) thiết bị là nhỏ nhất. Biết rằng mỗi thiết bị chỉ gắn một bộ nguồn duy nhất.

Yêu cầu

  • Hãy chỉ ra giá trị tổng độ gây hại nhỏ nhất của \(k\) thiết bị.

Dữ liệu vào

  • Dòng đầu tiên gồm \(2\) số nguyên \(n\) và \(k\);
  • Dòng thứ \(2\) gồm \(n\) số nguyên \(p_1, p_2,..., p_n\) là công suất của \(n\) bộ nguồn;
  • Dòng thứ \(3\) gồm \(k\) số nguyên \(t_1, t_2,..., t_k\) là công suất theo lý thuyết của \(k\) thiết bị.
  • Các số trên một dòng cách nhau bởi một kí tự trắng.

Dữ liệu đảm bảo:

  • \(1 \le k \le n \le 10^3\);
  • \(1 \le t_i \le 10^2\);
  • \(1 \le p_j \le 10^2\).

Dữ liệu ra

  • Một số nguyên duy nhất thỏa yêu cầu bài toán.

Ràng buộc

  • Có \(25\%\) số test có \(1 \le k \le n \le 20\);
  • Có \(75\%\) số test còn lại không có ràng buộc gì thêm.

Input 1

5 3
1 3 7 3 6
2 5 1

Output 1

2

Giải thích

Bộ nguồn số \(1\) gắn vào thiết bị số \(3\), bộ nguồn số \(2\) gắn vào thiết bị số \(1\), bộ nguồn số \(5\) gắn vào thiết bị số \(2\) với tổng độ gây hại nhỏ nhất cho cả 3 thiết bị là \(2\).


Nhận xét

Không có ý kiến tại thời điểm này.