Elearning CodePath – CTP Online Judge

Tìm cặp có tổng bằng K

TP_Find_2

🟢 Hard #Hash #Sorting

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho dãy số nguyên `A` gồm `N` phần tử và một số nguyên `K`.  
Hãy viết chương trình tìm **một cặp phần tử** `X, Y` trong dãy `A` sao cho `X + Y = K`.

**Quy tắc chọn cặp duy nhất để in ra:**

- Gọi cặp vị trí là `(i, j)` với `1 ≤ i < j ≤ N`, `A[i] + A[j] = K`.
- Chọn cặp có chỉ số trái nhỏ nhất `i`.

---

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

Dữ liệu vào từ file `TP_Find_2.inp` gồm:

* **Dòng 1:** Hai số nguyên `N` và `K` cách nhau một khoảng trắng.  
* **Dòng 2:** `N` số nguyên `A[1], A[2], …, A[N]` cách nhau một khoảng trắng.

**Ràng buộc:**
```
1 ≤ N ≤ 1,000,000
0 ≤ A[i] ≤ 1,000,000
-1,000,000 ≤ K ≤ 1,000,000
```

> Ghi chú: Biên `K` có thể âm/ dương/ 0; vẫn áp dụng quy tắc chọn cặp như trên.

---

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

Ghi ra file `TP_Find_2.out` hai số `X Y` (giá trị phần tử) cách nhau một khoảng trắng — tương ứng với cặp thỏa mãn quy tắc chọn ở trên.  
Nếu không tồn tại cặp thỏa mãn, in:
```
-1 -1
```

---

### ✨ Ví dụ

| Input (`TP_Find_2.inp`) | Output (`TP_Find_2.out`) |
| :--- | :--- |
| `5 9`<br>`1 2 4 5 7` | `2 7` |
| `7 8`<br>`4 5 7 6 3 4 0` | `4 4` |
| `5 10`<br>`1 2 4 5 7` | `-1 -1` |

---

### 🧪 Phân Subtask & Ràng buộc

| Subtask | Ràng buộc bổ sung | Gợi ý thuật toán |
| :--- | :--- | :--- |
| **Subtask 1 (30 điểm)** | `N ≤ 3000` | **Vét cạn O(N²)**|
| **Subtask 2 (70 điểm)** | `N ≤ 1,000,000` | **Tối ưu O(N)** với **Hash Map** |

---

### 💡 Gợi ý

- Với Subtask 2, **không nên** sắp xếp mảng nếu bạn phải bảo toàn quy tắc chọn theo **thứ tự xuất hiện gốc**.  
- Dùng `unordered_map`/`dictionary` để lưu tần suất hoặc lần gặp đầu tiên của mỗi giá trị đã quét.

✅ Đã AC: 14 / 46 submissions

📘 Lời giải

```
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#define ll long long
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

// freopen("TP_Find_2.inp", "r", stdin);
    // freopen("TP_Find_2.out", "w", stdout);

ll N, K;
    if (!(cin >> N >> K)) return 0;

vector<ll> A(N + 1);

ll best_i = N + 1; 
    ll best_j = N + 1;

unordered_map<ll, int> mp; 
    
    for (int j = 1; j <= N; ++j) {
        cin >> A[j]; 
        
        ll Aj = A[j];
        ll X = K - Aj; 
        
       
        if (mp.count(X)) {
            int current_i = mp.at(X); 
            int current_j = j;
            
            
            if (current_i < best_i) {
                best_i = current_i;
                best_j = current_j; 
            }
            
        }

if (mp.count(Aj) == 0) {
            mp[Aj] = j;
        }
    }
    
    
    if (best_i <= N) { 
        cout << A[best_i] << " " << A[best_j] << "\n";
    } else {
        cout << "-1 -1\n";
    }

return 0;
}
```