Elearning CodePath – CTP Online Judge

Bán vé sân vận động

STADIUM

🟢 Medium #Greedy #Queue #Priority Queue #Interval

### 📌 Thông tin chung

### 📝 Bài toán

Sân vận động Lạch Tray hiện có $m$ hàng ghế trống. Hàng ghế thứ $i$ còn trống $x_i$ ghế. Có $n$ người đang xếp hàng mua vé. Mỗi người mua đúng 1 vé. Giá vé được quy định: Tại thời điểm mua, nếu người mua nhận vé ở hàng $i$ thì giá vé bằng số ghế còn trống của hàng $i$.
Yêu cầu: Hãy tìm cách bán vé sao cho tổng số tiền thu được là lớn nhất.

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

Dữ liệu vào từ file văn bản STADIUM.INP:
* Dòng 1: Hai số nguyên dương $m, n$ ($1 \le m, n \le 10^6$).
* Dòng tiếp theo: Chứa dãy số $x_1, x_2, \dots, x_m$ ($0 \le x_i \le 10^6, \sum x_i \ge n$).

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

Ghi ra file văn bản STADIUM.OUT một số nguyên duy nhất là số tiền lớn nhất thu được.

### ✨ Ví dụ

| STADIUM.INP | STADIUM.OUT |
| :--- | :--- |
| 3 4 <br> 1 2 4 | 11 |

**Giải thích ví dụ:**
Hàng ghế trống: {1, 2, 4}. Bán cho 4 người:
1. Người 1: Chọn hàng 3 (còn 4 ghế) -> Giá 4. Hàng ghế còn: {1, 2, 3}.
2. Người 2: Chọn hàng 3 (còn 3 ghế) -> Giá 3. Hàng ghế còn: {1, 2, 2}.
3. Người 3: Chọn hàng 2 hoặc 3 (còn 2 ghế) -> Giá 2. Hàng ghế còn: {1, 1, 2}.
4. Người 4: Chọn hàng 3 (còn 2 ghế) -> Giá 2.
Tổng tiền: 4 + 3 + 2 + 2 = 11.

### 🏷 Subtasks

* Subtask 1 (30%): $m, n \le 1000$
* Subtask 2 (70%): $m, n \le 10^6$

✅ Đã AC: 4 / 6 submissions