Lời giải chi tiết

Ý tưởng chính:

• Chia cách di chuyển của Bình làm 3 trường hợp: di chuyển hẳn qua trái, di chuyển hẳn qua phải và đi sang trải một phần rồi quay lại sang phải (hoặc ngược lại).
• Với hai trường hợp đầu tiên, cần kiểm tra xem phía bên đó có ít hơn \(k\) cây nến hay không. Nếu đúng thì phải loại bỏ hai trường hợp này. Ngược lại thì ta sẽ lấy vị trí của cây nến thứ \(k\) tính từ giữa của một trong hai phía và lưu lại kết quả để so sánh.
• Với trường hợp thứ ba, từ vị trí ở giữa, ta sử dụng kĩ thuật hai con trỏ để tìm được đoạn con chứa \(k\) cây nến sao cho quãng đường di chuyển từ 0 tới vị trí cây nến bên trái và bên phải được phù hợp. Sau đó, tùy thuộc vào việc bên nào đi ngắn hơn thì ta sẽ nhân đôi hướng đó, rồi cộng lại với nhau.
• So sánh 3 trường hợp kể trên với nhau, trường hợp nào ngắn nhất sẽ là kết quả của bài toán.

Đăng ký khóa học: https://www.facebook.com/clblaptrinhfullhouse

SĐT liên hệ: 0372229686

Youtube: CLB Lập Trình Full House

Fullhouse dev đồng hành trên từng dòng code