ELEVATOR - Thang máy
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Có ~N~ người đang đứng chờ thang máy, người thứ ~i~ muốn đi đến tằng thứ ~p_i~. Không may, chỉ có một cái thang máy, và nó có thể chứa tối đa ~K~ người, thời gian để đi từ tầng ~a~ đến ~b~ là ~|a − b|~. Ban đầu, thang máy dừng ở tầng một và mọi người đều đứng ở tầng một. Hỏi thang máy cần ít nhất bao nhiêu thời gian để ~N~ người đều tới được tầng mình muốn và thang máy quay trở lại tầng một?
Input
- Dòng đầu tiên, chứa số nguyên dương ~N, K~;
- Dòng tiếp theo, chứa ~N~ số nguyên ~p_i~ - tầng mà người thứ ~i~ muốn tới.
Giới hạn:
- ~1 ≤ N, K ≤ 2000; 1 ≤ p_i ≤ 2000~.
Output
- Gồm một dòng duy nhất,chứa số nguyên duy nhất là đáp án của bộ test.
Sample
Input #1
3 2
2 3 4
Output #1
8
Problem source: Kc97ble - Free Contest
Bình luận
Bài này tương đối dễ, tuy nhiên nếu "bầu bí" thì bạn có thể đọc qua cách giải của mình.
Ý tưởng: Cách đi thang máy của bài này hơi kì (khác so với thực tế :>). OK, bây giờ ta xét ví dụ đó là có 3 người với lần lượt các tầng muốn đi là [2, 3, 4]. Tuy nhiên, thang chở tối đa 2 người, vậy có 2 câu hỏi đặt ra.
Thứ nhất cần trở bao nhiêu lượt ?: Câu trả lời sẽ là (n / k) nếu n % k == 0 và (n / k) + 1 nếu n % k != 0.
Thứ hai là cần trở 2 người nào (ý là muốn đến tầng nào) sao cho tối ưu time nhất. Ý tưởng của mình sẽ là cứ đưa ông cần lên tầng cao nhất lên trước, sau đó giảm dần. Vậy với k = 2, mình sẽ đưa 2 ông muốn lên tầng 3 và 4 trước.
Từ 1 -> 3 sẽ mất 2 (time), tiếp túc từ 3 -> 4 mất 1 (time) và từ 4 -> 1 sẽ mất 3 (time) vậy tổng là 6 (time), tuy nhiên tính vậy rõ ràng là hơi loằng ngoằng, ta sẽ thấy ngay tổng thời gian mất sẽ là (1 -> 4 chiều đi) + (4 -> 1 chiều về) = 2 * (1 -> 4) = 3 * 2 = 6. Vậy xong 1 lượt, còn 1 lượt nữa.
Ta đưa nốt người này lên tầng 2 và quay lại tầng 1 vậy là mất 2 (time) nữa.
Tổng time ở các lượt sẽ là kết quả của bài toán N = 6 + 2 = 8.
Note: Để dễ duyệt mấy ông muốn đi lên tầng cao nhất, thì ta sort lại mảng nhé.