Tóm tắt đề bài

Cho số nguyên dương \(S\) và ma trận \(A\) kích thước \(m \times n\) (\(m,n \le 10^3\)), mỗi phần tử \(a_{ij} \le 10^9\).
Hãy tìm tổng lớn nhất của 2 phần tử ở 2 vị trí khác nhau sao cho tổng đó không vượt quá \(S\). Nếu không tồn tại cặp nào thỏa mãn, in ra \(-1\).

Phân tích

• Số phần tử của ma trận là \(N = m \cdot n \le 10^6\).
• Bài toán trở thành:
  • Cho mảng \(N\) số dương, tìm $ \max(a_p + a_q)$ với \(p \ne q\) và \(a_p + a_q \le S\).
• Không thể duyệt mọi cặp vì \(O(N^2)\) là quá lớn.
• Nhận xét quan trọng:
  • Nếu ta sắp xếp dãy, có thể dùng kỹ thuật hai con trỏ (two pointers) để tìm tổng lớn nhất \(\le S\) trong \(O(N)\) sau khi sort.

Hướng giải quyết

Nhận xét

• Sau khi sort tăng dần: \(b_0 \le b_1 \le \dots \le b_{N-1}\).
• Dùng hai chỉ số:
  • \(l\) bắt đầu từ đầu (nhỏ nhất)
  • \(r\) bắt đầu từ cuối (lớn nhất)
• Với mỗi cặp \((l,r)\):
  • Nếu \(b_l + b_r \le S\) thì đây là một ứng viên tốt (vì \(b_r\) đang lớn nhất có thể với \(l\) hiện tại), ta cập nhật đáp án và tăng \(l\) để thử tổng lớn hơn.
  • Nếu \(b_l + b_r > S\) thì tổng quá lớn, cần giảm \(r\).

Thuật toán

1. Đọc \(m, n, S\).
2. Đưa toàn bộ \(m \cdot n\) phần tử vào một mảng \(b\).
3. Nếu \(N < 2\) thì in \(-1\).
4. Sắp xếp mảng \(b\) tăng dần.
5. Khởi tạo:
   • \(l = 0\), \(r = N-1\)
   • ans = -1
6. Trong khi \(l < r\):
   • Tính \(sum = b_l + b_r\)
     • Nếu \(sum \le S\):
       • ans = max(ans, sum)
       • \(l \leftarrow l + 1\)
     • Ngược lại:
       • \(r \leftarrow r - 1\)
7. In ans.

Vì sao đúng?

• Khi \(b_l + b_r \le S\), với cùng \(l\), mọi \(r' < r\) sẽ cho tổng \(\le b_l + b_r\) nên không tốt hơn; do đó ta nên tăng \(l\) để có cơ hội tăng tổng.
• Khi \(b_l + b_r > S\), với cùng \(r\), mọi \(l' > l\) chỉ làm tổng tăng, càng vượt \(S\); do đó bắt buộc phải giảm \(r\).

Độ phức tạp

• Sắp xếp: \(O(N \log N)\) với \(N = m \cdot n \le 10^6\).
• Hai con trỏ: \(O(N)\).
• Bộ nhớ: \(O(N)\) để lưu mảng.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    long long S;
    cin >> m >> n >> S;

    int N = m * n;
    vector<long long> b;
    b.reserve(N);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            long long x;
            cin >> x;
            b.push_back(x);
        }
    }

    if ((int)b.size() < 2) {
        cout << -1 << "\n";
        return 0;
    }

    sort(b.begin(), b.end());

    int l = 0, r = (int)b.size() - 1;
    long long ans = -1;

    while (l < r) {
        long long sum = b[l] + b[r];
        if (sum <= S) {
            ans = max(ans, sum);
            l++; // thử tăng tổng bằng cách tăng phần tử nhỏ hơn
        } else {
            r--; // giảm tổng bằng cách giảm phần tử lớn hơn
        }
    }

    cout << ans << "\n";
    return 0;
}