Elearning CodePath – CTP Online Judge

Bánh quy

🟢 Hard #Greedy #Priority Queue

### 📌 Thông tin chung

### Bài toán

HD có $N$ chiếc bánh quy, chiếc bánh thứ $i$ có độ ngọt là $A_i$. HD muốn tất cả các bánh quy của mình đều đạt được độ ngọt tối thiểu là $K$. Để thực hiện điều này, anh ấy lặp lại thao tác sau:

1. Chọn hai chiếc bánh quy có độ ngọt nhỏ nhất ($min\_1$) và nhỏ nhì ($min\_2$).
2. Trộn chúng lại và nướng thành một chiếc bánh mới có độ ngọt được tính theo công thức:
   $$Độ\ ngọt\ mới = 1 \times min\_1 + 2 \times min\_2$$

Quá trình này lặp lại cho đến khi tất cả các chiếc bánh trong khay đều có độ ngọt lớn hơn hoặc bằng $K$.

Yêu cầu: Hãy xác định số lần HD cần nướng lại bánh. Nếu sau khi đã trộn hết các bánh mà vẫn không thể đạt được độ ngọt $K$ cho tất cả các bánh, hãy in ra -1.

### Định dạng Đầu vào

Dữ liệu vào từ file COOKIES.INP:
* Dòng 1: Hai số nguyên dương $N$ và $K$.
* Dòng 2: Chứa $N$ số nguyên $A_1, A_2, \dots, A_n$ là độ ngọt ban đầu của các chiếc bánh.

### Giới hạn

* $2 \le N \le 10^6$.
* $0 \le K \le 10^9$.
* $0 \le A_i \le 10^9$.

### Định dạng Đầu ra

Ghi ra file COOKIES.OUT một số nguyên duy nhất là số lần nướng lại bánh hoặc -1 nếu không thể thực hiện được.

### ✨ Ví dụ

| COOKIES.INP | COOKIES.OUT | Giải thích |
| :--- | :--- | :--- |
| 6 7 <br> 1 2 3 9 10 12 | 2 | - Lần 1: Trộn 1 và 2 $\rightarrow 1 + 2 \times 2 = 5$. Khay bánh: {3, 5, 9, 10, 12}. <br> - Lần 2: Trộn 3 và 5 $\rightarrow 3 + 2 \times 5 = 13$. Khay bánh: {9, 10, 12, 13}. <br> Tất cả bánh đều $\ge 7$. |

### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $N \le 1000$ | 40% |
| 2 | $N \le 10^6$ | 60% |

✅ Đã AC: 4 / 13 submissions