trang chủ / đề bài / almostgood

Que gần tốt

Đề bài

Mô tả

Bạn được cho n chiếc que có độ dài nguyên dương a1,a2,…,an.

Với mỗi chiếc que, bạn có thể đổi độ dài của nó thành một số nguyên dương bất kỳ (kéo dài ra hoặc rút ngắn lại). Chi phí để đổi độ dài một chiếc que từ a thành b là |a−b|.

Độ dài ai được gọi là gần tốt với số nguyên t nếu |ai−t|≤1.

Hãy đổi độ dài của một số chiếc que (có thể là tất cả, cũng có thể không đổi cái nào) sao cho tồn tại một số nguyên dương t mà mọi chiếc que đều gần tốt với t, đồng thời tổng chi phí là nhỏ nhất có thể. Giá trị t không được cho trước, bạn được tự chọn t là số nguyên dương bất kỳ.

Nếu có nhiều giá trị t cùng cho tổng chi phí nhỏ nhất, in ra giá trị nào cũng được.

Dữ liệu vào

  • Dòng đầu tiên chứa một số nguyên n: số chiếc que.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an: độ dài của các chiếc que.

Dữ liệu ra

In ra một dòng gồm hai số nguyên cách nhau bởi dấu cách: giá trị t và tổng chi phí nhỏ nhất tương ứng.

Ràng buộc

  • 1≤n≤1000
  • 1≤ai≤100

Ví dụ

Input Output Giải thích
3
10 1 4
3 7 Đổi que dài 1 thành 2 và que dài 10 thành 4, chi phí ‖1−2‖+‖10−4‖=1+6=7. Bộ độ dài thu được [2,4,4] đều gần tốt với t=3.
5
1 1 2 2 3
2 0 Các độ dài đã gần tốt với t=2 sẵn rồi, không cần đổi gì nên chi phí bằng 0.
4
1 1 5 5
2 4 Với t=2, hai que dài 5 cần rút về 3, mỗi que tốn 2, tổng là 4. Chọn t=3 cũng cho tổng chi phí 4 (mỗi que dài 1 kéo lên 2, mỗi que dài 5 rút về 4), nên in t nào trong hai giá trị đó cũng được chấp nhận.

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