Xích mèo


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 10M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Vào ngày sinh nhật, Tý được tặng một bé mèo vô cùng đáng yêu. Anh sợ bé bỏ đi nên đã mua các đoạn dây xích về để sử dụng.

Các mắt xích có thể tháo ra và lắp lại. Tý muốn nối tất cả các đoạn dây xích lại với nhau với số lần tháo lắp một mắt xích là ít nhất.

Các bạn hãy giúp Tý nhé.

Input:

Dòng đầu chứa số n là số đoạn xích (2<=n<=500000)

Dòng thứ 2 chứa n số nguyên, L[i] là độ dài của n đoạn xích thứ i (1<=L[i]<=1000000)

Output:

Số lần tháo lắp ít nhất để nối tất cả đoạn xích lại với nhau.

Chú ý: tháo và lắp được tính 1 lần.

Ví dụ:

Input:

3

1 1 1

Output:

1


Comments


  • 2
    sguenm  commented on June 23, 2021, 3:30 a.m.

    ai giải thích ví dụ này giúp mình được k ạ


    • 0
      CThành_CNTT6_K61  commented on June 23, 2021, 7:03 a.m.

      1 mắt xích đầu tiên nối đc 2 cái mắt xích tiếp theo


      • 3
        sguenm  commented on June 23, 2021, 10:30 a.m.

        Hehe, cảm ơn nhá, cơ mà t chưa hình dung ra được mắt xích là như nào, để nghĩ lại