# 🧩 Solution bài toán Nối Xích
📌 **Link đề bài: https://lqdoj.edu.vn/problem/noixich**

---
## 🔍 Tóm tắt đề bài

- Có $N$ đoạn xích $(N ≤ 200000)$, mỗi đoạn là một chuỗi liên tiếp các mắt xích, ngăn cách nhau bởi dấu cách.
- Mỗi đoạn có thể có độ dài khác nhau (tức là số lượng mắt xích khác nhau).
- Ta có thể **nối 2 đoạn xích lại thành 1 đoạn** bằng cách:
- **Cắt một mắt xích** từ một đoạn bất kỳ (độ dài đoạn đó giảm đi 1).
- **Nối** đoạn vừa bị cắt với 2 đoạn khác để ghép lại.
- Tổng thời gian thực hiện thao tác này là **1 đơn vị thời gian**.

📷 Ví dụ minh họa:

---

## 🎯 Yêu cầu

> Tính **thời gian ít nhất** để nối tất cả các đoạn xích thành một đoạn duy nhất.

---

## 🧠 Ý tưởng:
Chúng ta sẽ dùng thuật toán **Tham Lam** để giải bài toán này.

- Đầu tiên ta sẽ tính thời gian **tối đa** để nối các đoạn xích lại thành $1$ đoạn hay nói cách khác là nối đoạn xích $1$ với đoạn xích $2$ rồi lấy đoạn xích $2$ nối với đoạn xích $3$ $\dots$ cho tới đoạn xích $n$. Thời gian tối đa để nối $n$ đoạn xích là $n - 1$ đơn vị
- Vậy làm sao để tối ưu thời gian lớn nhất là $n - 1$ xuống thấp nhất có thể?
- **Nhận xét:** Giả sử có $3$ đoạn xích $a, b, c$ có độ dài là $1, 2$ và $3$. Ta sẽ lấy đoạn xích $a$ nối $b$ và $c$ lại với nhau thành đoạn xích độ dài $5$. Lúc này ta không chỉ nối $2$ đoạn $b$ và $c$ với nhau mà nối luôn cả $a$ chỉ mất thời gian là $1$. Thay vì ta nối $a$ và $b$ rồi nối $c$ mất thời gian là $2$.
- **Suy ra:** Khi ta cắt hết càng nhiều đoạn xích thì thời gian nối tất cả đoạn xích càng nhỏ.
$\rightarrow$ Ta sẽ chọn các đoạn xích **ngắn nhất** và cắt để nối các đoạn xích khác.

## ✅️ Thuật toán:
- Gọi thời gian tối đa để nối các đoạn xích với nhau là $x$ $(x = n - 1)$.
- Để chọn ra các đoạn xích ngắn nhất thì ta sẽ **sort tăng dần** độ dài các đoạn.
- Tiếp theo, mỗi lượt ta sẽ trừ $a_i \text{ } (0 \leq i < n)$ và $x$ đi $1$ (cắt và nối $2$ đoạn khác) và tăng đáp án lên $1$. Mỗi lượt, thời gian sẽ được tối ưu $1$ đơn vị. Nếu $a_i = 0$, tức là đã cắt hết đoạn thứ $i$ $\rightarrow$ $x$ trừ đi $1$ vì giảm thêm $1$ lần nối. Sau đó chuyển đến đoạn $i + 1$ rồi tiếp tục cắt.
- Lặp lại các bước đó cho đến khi chỉ còn $1$ đoạn xích.
### 📌 Code tham khảo (chưa chắc AC):

signed main() {
    n = Readint();
    a = ReadList();
    sort(a, a + n);
	
    x = n - 1;
    i = 0, kq = 0;

    while (i < n){
        if (a[i] > 0){
            x --;
            a[i] --;
            kq ++;
        }
		
        if (a[i] == 0) i ++, x --;

        if (sl == 0) break;
    }

    cout << kq;
    return 0;
}