Tổ chức sơ tán

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Java, Pascal, Perl, PHP, Python, Sed, TCL, Text

Trong giai đoạn kháng chiến chống Đế quốc Mỹ, nước ta thường xuyên phải hứng chịu mưa bom bão đạn của kẻ thù. Khi phát hiện máy bay địch sắp sửa tiến hành oanh tạc, người dân sẽ cần phải tìm đến trú ẩn trong một trong các hầm trú ẩn được xây dựng sẵn từ trước để tránh bom mìn. Có N người và M hầm trú ẩn ở các tọa độ khác nhau trên cùng một đường thẳng. Mỗi người sẽ cần phải chạy tới một hầm trú ẩn nào đấy để lánh nạn khi sắp sửa có đánh bom và một hầm có thể cho phép nhiều người tới lánh nạn cùng một lúc. Thời gian di chuyển của người đang ở tọa độ i tới hầm trú ẩn ở tọa độ j là |i-j|. Tính tổng thời gian di chuyển ngắn nhất để cả N người đều tìm được nơi trú ẩn.

Dữ liệu vào gồm 3 dòng:

  • Dòng đầu tiên gồm hai số nguyên dương N và M (N,M≤100), lần lượt là số người và số hầm trú ẩn.
  • Dòng thứ hai gồm N số nguyên không âm, là tọa độ của N người. Lưu ý có thể có nhiều người ở cùng một tọa độ.
  • Dòng thứ ba gồm M số nguyên không âm, là tọa độ của M hầm trú ẩn. Dữ liệu đảm bảo M tọa độ này là phân biệt (không có hai hầm trú ẩn nào ở cùng một vị trí).
  • Các tọa độ không vượt quá ~10^4~.

Dữ liệu ra: gồm một số nguyên duy nhất là tổng thời gian di chuyển ngắn nhất để cả N người đều tìm được nơi trú ẩn.

  • Giới hạn: 50% số test có M=1.
Ví dụ:
INPUT
5 3
2 9 5 7 9
1 5 12
OUTPUT
9

Giải thích:

  • Người ở tọa độ 2 sẽ đi đến hầm trú ẩn ở tọa độ 1 với thời gian là |2-1|=1.
  • Người ở tọa độ 5 sẽ đi đến hầm trú ẩn ở tọa độ 5 với thời gian là |5-5|=0 .
  • 2 người ở tọa độ 9 sẽ đi đến hầm trú ẩn ở tọa độ 12 với tổng thời gian là 2*|9-12|=6.
  • Người ở tọa độ 7 sẽ đi đến hầm trú ẩn ở tọa độ 5 với thời gian là |7-5|=2.

Vì vậy, tổng thời gian di chuyển của phương án này là 1+0+6+2=9. Đây cũng chính là phương án tối ưu.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.