H
hai6f2009
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Có N chuỗi dây xích trên căn gác xép. Mỗi chuỗi dây xích gồm có một số mắt xích kết nối với nhau, mỗi mắt xích có thể kết nối với nhiều nhất hai mắt xích liền kề. Mỗi mắt xích có thể mở hoặc đóng, vì vậy nó có thể tách một dây xích ra thành nhiều dây xích khác nhau hoặc cũng có thể kết nối các dây xích khác nhau thành một dây xích dài hơn. Một người muốn kết nối tất cả các chuỗi dây xích mà anh ta đang có thành một dây xích lớn, với số mắt xích được dùng để mở và đóng là ít nhất có thể. Ví dụ, nếu người đó có 3 chuỗi dây xích, mỗi chuỗi gồm có một mắt xích, thì anh ấy có thể mở một mắt xích để kết nối hai mắt xích còn lại rồi sau đó đóng mắt xích đó lại.
Cho số lượng chuỗi dây xích và độ dài của mỗi chuỗi, tìm số mắt xích nhỏ nhất để người đó có thể mở và đóng để kết nối tất cả chuỗi dây xích thành một chuỗi.
- Input: File NOIXICH.INP
+ Dòng đầu tiên chứa số nguyên dương N (2 ≤ N ≤ 500 000) là số lượng chuỗi dây xích.
+ Dòng thứ hai chứa N số nguyên dương Li (1 ≤ Li ≤ 1 000 000), là độ dài (số mắt xích) của chuỗi dây xích thứ i
- Output: File NOIXICH.OUT
Gồm một dòng duy nhất chứa số mắt xích nhỏ nhất tìm được.
Ví dụ:
Input
2
3 3
Output
1
Input
3
1 1 1
Output
1
Input
5
4 3 5 7 9
Output
3
- Input: File NOIXICH.INP
+ Dòng đầu tiên chứa số nguyên dương N (2 ≤ N ≤ 500 000) là số lượng chuỗi dây xích.
+ Dòng thứ hai chứa N số nguyên dương Li (1 ≤ Li ≤ 1 000 000), là độ dài (số mắt xích) của chuỗi dây xích thứ i
- Output: File NOIXICH.OUT
Gồm một dòng duy nhất chứa số mắt xích nhỏ nhất tìm được.
Ví dụ:
Input
2
3 3
Output
1
Input
3
1 1 1
Output
1
Input
5
4 3 5 7 9
Output
3