Nối xích
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Người ta có N đoạn dây xích \((N \leq 200000)\), mỗi đoạn dây xích là chuỗi các mắt xích được nối với nhau. Các đoạn dây xích này tách rời nhau. Mỗi đoạn mắt xích có không quá \(200000\) mắt xích. Bằng cách cắt ra một mắt xích, sau đó hàn lại, ta có thể nối hai dây xích thành một đoạn. Thời gian để cắt và hàn mỗi mắt xích là \(1\) đơn vị thời gian và được xem là bằng nhau với mọi mắt xích. Nhiêm vụ của bạn là phải nối chúng lại thành một đoạn dây xích duy nhất với thời gian ít nhất( hay số mắt xích bị cắt và hàn lại là ít nhất).
Input
- Dòng đầu tiên là số \(N\), số đoạn xích. Một dòng tiếp theo ghi \(N\) số nguyên dương, số thứ i là số mắt xích có trong đoạn xích thứ \(i(i \le i \le N)\). Hai số cạnh nhau trên cùng một dòng cách nhau ít nhất một dấu cách.
Output
- Một dòng duy nhất là số đơn vị thời gian mà bạn cần để nối \(N\) đoạn xích đã cho.
Example
Test 1
Input
3
2 3 4Output
2
Bình luận
Gợi ý
Nhớ ứng dụng thực tế nha. Mình cắt hết toàn bộ một dây xích, lấy các mắt xích của nó để nối thì mình sẽ bớt được 1 đoạn xích cần nối
em chịu, chả hiểu bài này làm sao
mình chẳng hiểu đề bài yêu cầu gì cả
Đề yêu cầu mình làm gì vậy ạ, bạn nào hiểu đề giải thích cho mình với:(
Ai có thể giải thích đề rõ ràng giúp mình được không?