trang chủ / đề bài / icpcwf23_j

Qua cầu ban đêm

Đề bài

Mô tả

Một nhóm người đi bộ đến một con sông vào ban đêm. Họ muốn đi qua một cây cầu, nhưng cây cầu chỉ chịu được một số lượng người giới hạn cùng lúc. Cả nhóm chỉ có đúng một ngọn đuốc, và mỗi lần đi qua cầu đều phải mang theo đuốc. Mỗi người cần một khoảng thời gian nhất định để đi qua cầu; một nhóm đi cùng nhau phải đi theo tốc độ của người chậm nhất trong nhóm. Hỏi cần ít nhất bao nhiêu thời gian để tất cả mọi người sang được bờ bên kia?

Ví dụ, ở ví dụ thứ nhất, cây cầu chịu được 2 người cùng lúc và có 4 người với thời gian qua cầu lần lượt là 1 phút, 2 phút, 5 phút và 10 phút. Thời gian ngắn nhất là 17 phút, đạt được bằng chuỗi các lượt qua cầu sau. Thứ nhất, hai người nhanh nhất đi sang trong 2 phút. Thứ hai, người nhanh nhất quay lại trong 1 phút. Thứ ba, hai người chậm nhất đi sang trong 10 phút. Thứ tư, người nhanh thứ hai quay lại trong 2 phút. Thứ năm, hai người nhanh nhất đi sang trong 2 phút.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và c, trong đó n (2≤n≤104) là số người, và c (2≤c≤104) là số người tối đa cây cầu chịu được cùng lúc.

Dòng tiếp theo chứa n số nguyên t1,…,tn (1≤ti≤109 với mọi i). Người thứ i cần thời gian ti để đi qua cầu.

Dữ liệu ra

In ra tổng thời gian nhỏ nhất để cả nhóm đi qua cầu.

Ràng buộc

  • 2≤n≤104.
  • 2≤c≤104.
  • 1≤ti≤109.

Ví dụ

Input Output Giải thích
4 2
1 2 10 5
17 Gọi mỗi người theo thời gian qua cầu của họ. Lần lượt: {1,2} sang (2 phút), 1 quay lại (1 phút), {5,10} sang (10 phút), 2 quay lại (2 phút), {1,2} sang (2 phút). Tổng 17 phút.
4 6
1 2 10 5
10 Cầu chịu được 6 người nên cả 4 người đi sang cùng một lượt, mất 10 phút.

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