trang chủ / đề bài / icpc19_nat_g

Tụ họp ở Yorknew

Đề bài

Mô tả

Các Thợ săn từ khắp nơi trên thế giới đang đổ về Yorknew, nơi diễn ra "Kỳ thi Lập trình Thợ săn Quốc tế 2020". Vì Gon đã vượt qua vòng cuối của Kỳ thi Thợ săn và trở thành Thợ săn, có thể bạn sẽ gặp Gon ở Yorknew!

Có đúng một con đường dẫn tới Yorknew: một con đường hẹp và dài vô hạn. Để đơn giản, có thể coi con đường là một đường thẳng.

Có h Thợ săn đang đi tới thành phố Yorknew. Thợ săn thứ i hiện đang ở vị trí xi. Thành phố Yorknew nằm ở vị trí 0. Các Thợ săn đều đi rất nhanh: họ di chuyển với vận tốc 1 đơn vị mỗi giây.

Để tránh ùn tắc, ban quản lý thành phố Yorknew quyết định xây hai cổng dịch chuyển. Dịch chuyển từ cổng này sang cổng kia mất đúng 0 giây.

Ban quản lý muốn đặt hai cổng tại hai vị trí nguyên trên con đường sao cho tổng thời gian để cả h Thợ săn tới được thành phố Yorknew là nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa đúng một số nguyên h, số Thợ săn (1≤h≤105).

Dòng thứ hai chứa đúng h số nguyên: số thứ i là xi, vị trí hiện tại của Thợ săn thứ i (−109≤xi≤109).

Dữ liệu ra

In ra một số nguyên duy nhất là tổng thời gian để mọi Thợ săn tới được thành phố Yorknew.

Ràng buộc

  • 1≤h≤105
  • −109≤xi≤109

Ví dụ

Input Output Giải thích
3
4 5 6
2 Một cách đặt tối ưu là đặt hai cổng tại 0 và 5. Thời gian để ba Thợ săn tới Yorknew lần lượt là 1, 0 và 1, tổng là 1+0+1=2.
7
-7 -6 -5 1 2 3 20
24 Ví dụ bổ sung (không có trong đề gốc). Đặt hai cổng tại 0 và 20: Thợ săn ở 20 mất 0 giây, các Thợ săn còn lại đi bộ, tổng 7+6+5+1+2+3=24.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0