\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.99}}}}}\)

\(\color{#008b8b}{\text{Hướng dẫn}}\)

• Với mỗi vị trí \(l\) thỏa \((1 \leq l < n)\), tìm vị trí lớn nhất \(r\) thỏa \((l < r \leq n)\) sao cho \(a_l + a_r \leq X\)

• Nếu tồn tại một vị trí \(l\) sao cho tìm được vị trí \(r\) mà \(a_l + a_r = X\) thì xuất \(l\) và \(r\) và dừng chương trình.

• Ngược lại xuất ra "No solution"

\(\color{#008b8b}{\text{Tiếp cận}}\)

• Vì mảng tăng dần, nên duyệt từ \(l = 1 \rightarrow n\) thì giá trị \(a_l\) sẽ tăng dần nên \(a_r\) nhỏ dần để thỏa mãn \(a_l + a_r \leq x\) với \(r\) lớn nhất

• Vậy áp dụng kĩ thuật hai con trỏ, cho con trỏ \(l = 1 \rightarrow n\) và con trỏ \(r = n \rightarrow 1\). Nếu \(a_l + a_r \leq x\) rồi thì dừng, ngược lại tiếp túc giảm \(r\)

\(\color{#008b8b}{\text{Độ phức tạp}}\)

• Nhận dữ liệu mất \(O(n)\)

• Tìm kết quả mất \(O(l) + O(r) = O(n) + O(n)\)

• Xuất kết quả mất \(O(1)\)

\(\color{#008b8b}{\text{Code tham khảo }}\): Hai con trỏ

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n)\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>

using namespace std;

const int LIM = 1e6 + 16;

int a[LIM];
int main()
{
    int n, x;
    cin >> n >> x;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    for (int l = 1, r = n; l < r; ++l)
    {
        while (l < r - 1 && a[l] + a[r] > x) --r;
        if (a[l] + a[r] == x)
        {
            cout << l << ' ' << r;
            return 0;
        }
    }

    cout << "No solution";
    return 0;
}