Hướng dẫn giải của [Beginner Free Contest 03] LINETRIP
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Có N điểm trên trục Ox, một người xuất phát từ tọa độ 0, phải đi qua tất cả các điểm rồi quay về 0. Tìm độ dài ngắn nhất của hành trình.
Cách làm
Tìm điểm xa nhất bên trái L (nhỏ nhất, luôn không lớn hơn 0) và điểm xa nhất bên phải R (lớn nhất, luôn không nhỏ hơn 0). Người đi phải đến cả hai đầu và quay về 0, nên quãng đường ngắn nhất là 2(R - L). Ví dụ với các điểm -3, 4, 1 thì L = -3, R = 4 và kết quả là 27 = 14.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
// Tìm điểm xa nhất bên trái (<= 0) và xa nhất bên phải (>= 0) so với gốc 0
int trai = 0;
int phai = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x < trai) {
trai = x;
}
if (x > phai) {
phai = x;
}
}
// Người đi từ 0 phải đi qua cả hai đầu rồi quay về 0,
// nên quãng đường đi và về bằng 2 lần khoảng cách từ trai đến phai
cout << 2 * (phai - trai) << "\n";
return 0;
}
Bình luận