C++ Bài 10.E7: Chú chó chăn cừu


Submit solution

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 20M

Author:
Problem type

Chú chó chăn cừu tên One phát hiện ra rằng đàn cừu của mình luôn lang thang đến những nơi xa nhất trong trang trại! One cần sự giúp đỡ của bạn để dẫn chúng trở lại với nhau. Cánh đồng chính trong trang trại rất dài và hẹp - chúng ta có thể coi nó như một dãy số, trên đó một con cừu có thể chiếm một vị trí nguyên bất kỳ. Hiện tại, \(N\) con cừu đang ở các vị trí nguyên khác nhau, và One muốn chúng di chuyển để chiếm các vị trí liên tiếp (ví dụ, các vị trí \(3, 4, 5, 6, 7,\) và \(8\)).

Thật không may, các con cừu khá buồn ngủ, và One gặp khó khăn trong việc thu hút sự chú ý của chúng để làm cho chúng di chuyển. Tại bất kỳ thời điểm nào, chú chỉ có thể khiến một con cừu di chuyển nếu nó là một "điểm cuối" (hoặc là vị trí nhỏ nhất hoặc lớn nhất trong số tất cả các con cừu). Khi chú di chuyển một con cừu, chú có thể chỉ đạo nó di chuyển đến bất kỳ vị trí nguyên không có con cừu nào chiếm dụng miễn là tại vị trí mới này nó không còn là điểm cuối. Quan sát cho thấy theo thời gian, những di chuyển này có xu hướng đẩy các con cừu gần nhau hơn.

Hãy xác định số lượng di chuyển tối thiểu và tối đa có thể trước khi các con cừu được tập hợp vào \(N\) vị trí liên tiếp.

INPUT FORMAT

Dòng đầu tiên của đầu vào chứa \(N (3≤N≤10^5)\). Mỗi dòng tiếp theo chứa vị trí nguyên của một con cừu, trong khoảng từ \(1\) đến \(10^9\).

OUTPUT FORMAT

Dòng đầu tiên của đầu ra chứa số lượng di chuyển tối thiểu One cần thực hiện để tập hợp các con cừu lại với nhau. Dòng thứ hai của đầu ra chứa số lượng di chuyển tối đa mà One có thể thực hiện trước khi các con cừu được tập hợp lại với nhau.

Ví dụ:

Input
3
7
4
9
Output
1
2

Số lượng di chuyển tối thiểu là \(1\) nếu One di chuyển con cừu ở vị trí \(4\) đến vị trí \(8\), thì các con cừu sẽ ở các vị trí liên tiếp \(7, 8, 9\). Số lượng di chuyển tối đa là \(2\). Ví dụ, con cừu ở vị trí \(9\) có thể được di chuyển đến vị trí \(6\), sau đó con cừu ở vị trí \(7\) có thể được di chuyển đến vị trí \(5\).

Giải thích ví dụ mẫu
  • Ví dụ 1:
    • Dữ liệu: 3, 7 4 9
    • Giải thích: Để tập hợp ba con cừu vào các vị trí liên tiếp, tối thiểu là cần 1 di chuyển (chuyển cừu từ 4 đến 8). Tối đa có thể thực hiện 2 di chuyển, ví dụ chuyển cừu từ 9 đến 6, rồi chuyển cừu từ 7 đến 5.


Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House


Comments

There are no comments at the moment.