[Wecode 2015] Problem D: Khoảng cách
1. Đề bài Problem D Một du khách trúng một vé máy bay có thể bay đến bất kì thành phố nào trong nước, xuất phát từ thủ đô Hà Nội. Nhân dịp đó, người này muốn đi thêm các thành phố lân cận, nhưng vì lo lắng không đủ chi phí nên ông chỉ muốn tìm những thành phố gần nhau nhất . Tuy ...
1. Đề bài Problem D
Một du khách trúng một vé máy bay có thể bay đến bất kì thành phố nào trong nước, xuất phát từ thủ đô Hà Nội. Nhân dịp đó, người này muốn đi thêm các thành phố lân cận, nhưng vì lo lắng không đủ chi phí nên ông chỉ muốn tìm những thành phố gần nhau nhất . Tuy nhiên, hãng hàng không chỉ cho ông biết thông tin về khoảng cách giữa các thành phố so với thủ đô Hà Nội. Giả sử rằng tất cả các thành phố đề nằm trên một đường thẳng bắt đầu từ thủ đô Hà Nội, hãy giúp người này tìm ra khoảng cách ngắn nhất để có thể tính toán chi phí cho chuyến đi.
Input
Dữ liệu của Input bao gồm một vài bộ test. Mỗi bộ test bao gồm:
Dòng đầu tiên là số lượng thành phố N (1<N<106)
N dòng tiếp theo chứa khoảng cách của thành phố so với thủ đô.
Output
Với mỗi bộ test, Output bao gồm một số nguyên – Khoảng cách ngắn nhất tìm được.
Sample Input | Sample Output |
| 3 347 269 112 | 78 |
| 7 34 56 78 90 12 139 100 | 10 |
2. Code tham khảo Problem D
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <iostream> #include <algorithm> using namespace std; long n, a[1000000]; int main() { cin >> n; long i; for (i=0; i<n; i++) cin >> a[i]; sort(a,a+n); long res=2147483647; for (i=0; i<n-1; i++) if (res>a[i+1]-a[i]) res=a[i+1]-a[i]; cout << res; return 0; } |
