Thông tin Bài tập Bảng xếp hạng

https://meet.jit.si/DungTanKhoa

TAP XE (CSP - COUNTING STUDENT PAIRS)

Tóm tắt đề bài

Có \(n\) học sinh, học sinh thứ \(i\) có trọng lượng \(a_i\)[cite: 12]. Xe đạp có tải trọng tối đa là \(m\)[cite: 12].

  • Đếm số cặp chỉ số \((i, j)\) sao cho \(i < j\) và tổng trọng lượng hai bạn không vượt quá tải trọng xe: \(a_i + a_j \le m\)[cite: 12].
  • In ra một số nguyên duy nhất là số cặp tìm được[cite: 12].

Hướng giải quyết (Sắp xếp + Kỹ thuật Hai con trỏ / Two Pointers)

  1. Đọc hai số nguyên \(n, m\) và mảng trọng lượng \(a\) gồm \(n\) phần tử[cite: 12].
  2. Sắp xếp mảng tăng dần:
    • Dùng hàm sort(a, a + n) để sắp xếp các học sinh theo trọng lượng tăng dần.
    • Việc thay đổi thứ tự ban đầu không làm mất số lượng cặp thỏa mãn.
  3. Đếm bằng hai đầu mút (Two Pointers):
    • Đặt hai con trỏ: L = 0 (bạn nhẹ nhất còn lại) và R = n - 1 (bạn nặng nhất còn lại).
    • Khi L < R:
      • Nếu \(a[L] + a[R] \le m\):
        • Vì dãy đã sắp xếp, bạn nhẹ nhất \(a[L]\) ghép với bạn \(a[R]\) còn không quá tải trọng, thì bạn \(a[L]\) ghép với bất kỳ bạn nào đứng trước \(R\) (từ \(L + 1\) đến \(R\)) cũng đều thỏa mãn.
        • Số bạn có thể ghép cặp cùng với \(a[L]\) lúc này chính là \(R - L\) bạn.
        • Cộng \(R - L\) vào kết quả ans, rồi tăng L++ để xét bạn nhẹ tiếp theo.
      • Nếu \(a[L] + a[R] > m\):
        • Bạn \(a[R]\) quá nặng, ngay cả khi ghép với bạn nhẹ nhất \(a[L]\) mà vẫn bị quá tải, nên bạn \(a[R]\) không thể ghép với ai khác nữa.
        • Ta bỏ qua bạn này bằng cách giảm R--.
  4. Dùng kiểu dữ liệu long long cho biến đếm kết quả ans để tránh tràn số (vì số cặp tối đa có thể lên tới \(n(n - 1) / 2\)).

Điền vào chỗ trống

C++
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1000005;
int a[MAXN];

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

    int n;
    long long m;
    ... >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> a[...];
    }

    // Sắp xếp mảng trọng lượng tăng dần
    sort(a, a + ...);

    int L = 0;
    int R = n - 1;
    long long ans = 0;

    // Kỹ thuật hai con trỏ
    while (L < R) {
        if (a[L] + a[R] <= m) {
            ans += (R - ...);
            L...;
        } else {
            R...;
        }
    }

    cout << ... << "\n";

    return 0;
}
DEM CAP (PAIR SUM = K) 🐣🐣🐣

Tóm tắt đề bài

Cho dãy gồm \(n\) số nguyên dương không giảm \(a_1, a_2, \dots, a_n\) và số nguyên \(k\)[cite: 7].

  • Đếm số cặp chỉ số \((i, j)\) với \(i < j\) sao cho \(a_i + a_j = k\)[cite: 7].
  • Cặp \((i, j)\) và \((j, i)\) chỉ tính là 1 cặp[cite: 7].

Hướng giải quyết

  1. Nhập dãy số \(a\) (dãy đã được sắp xếp tăng dần sẵn)[cite: 7].
  2. Dùng hai con trỏ \(L = 0\) và \(R = n - 1\):
    • Nếu \(a[L] + a[R] < k\): Tăng \(L\).
    • Nếu \(a[L] + a[R] > k\): Giảm \(R\).
    • Nếu \(a[L] + a[R] == k\):
      • Nếu \(a[L] == a[R]\): Các số từ \(L\) đến \(R\) đều bằng nhau, số cặp là \(\frac{(R - L + 1) \times (R - L)}{2}\).
      • Nếu \(a[L] \neq a[R]\): Đếm số lượng phần tử bằng \(a[L]\) là \(c_1\), số lượng bằng \(a[R]\) là \(c_2\), sau đó cộng \(c_1 \times c_2\) vào đáp án.

Điền vào chỗ trống

C++
#include <iostream>
using namespace std;

const int MAXN = 1000005;
long long a[MAXN];

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

    int n;
    long long k;
    ... >> ... >> ...;

    for (int i = 0; i < n; i++) {
        cin >> a[...];
    }

    int L = ...;
    int R = ...;
    long long ans = 0;

    while (... < ...) {
        long long sum = a[...] + a[...];

        if (sum < k) {
            L...;
        } else if (sum > k) {
            R...;
        } else {
            // Truong hop 1: Tat ca phan tu tu L den R deu bang nhau
            if (a[L] == a[R]) {
                long long len = ... - ... + 1;
                ans += len * (len - 1) / ...;
                ...; // Dung vong lap vi da tinh xong toan bo doan con lai
            } else {
                // Truong hop 2: a[L] khac a[R]
                long long c1 = 0, c2 = 0;
                long long valL = a[L];
                long long valR = a[R];

                // Dem so phan tu bang valL
                while (L <= R && a[L] == ...) {
                    c1...;
                    L...;
                }

                // Dem so phan tu bang valR
                while (L <= R && a[R] == ...) {
                    c2...;
                    R...;
                }

                ans += ... * ...;
            }
        }
    }

    ... << ans << "\n";

    return 0;
}
DEM CAP DOI (HSG'20) - HAI CON TRO

Tóm tắt đề bài

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1, A_2, \dots, A_n\) và số nguyên \(x\).

  • Đếm số lượng cặp chỉ số \((i, j)\) với \(i < j\) sao cho \(A_i + A_j = x\).
  • Giới hạn: \(n \le 10^5\), \(x \le 10^6\), \(A_i \le 10^9\).

Hướng giải quyết bằng Hai con trỏ

  1. Dãy ban đầu chưa được sắp xếp, nên trước hết cần dùng sort(a, a + n) để đưa dãy về thứ tự tăng dần.
  2. Dùng hai con trỏ L = 0 và R = n - 1:
    • Nếu \(a[L] + a[R] < x\): Tổng nhỏ hơn yêu cầu \(\rightarrow\) tăng L++.
    • Nếu \(a[L] + a[R] > x\): Tổng lớn hơn yêu cầu \(\rightarrow\) giảm R--.
    • Nếu \(a[L] + a[R] == x\):
      • Nếu \(a[L] == a[R]\): Toàn bộ các phần tử từ \(L\) đến \(R\) đều bằng nhau, có \(len = R - L + 1\) phần tử. Số cặp tạo thành là \(\frac{len \times (len - 1)}{2}\). Sau đó dừng vòng lặp.
      • Nếu \(a[L] \neq a[R]\): Đếm số lượng phần tử bằng \(a[L]\) (gọi là \(c_1\)) và số lượng phần tử bằng \(a[R]\) (gọi là \(c_2\)). Cộng \(c_1 \times c_2\) vào kết quả, đồng thời di chuyển \(L\) và \(R\) tương ứng.

Điền vào chỗ trống

C++
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
long long a[MAXN];

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

    int n;
    long long x;
    ... >> n >> ...;

    for (int i = 0; i < n; i++) {
        cin >> a[...];
    }

    // Sắp xếp mảng tăng dần
    sort(a, a + ...);

    int L = ...;
    int R = ...;
    long long ans = 0;

    while (... < ...) {
        long long sum = a[...] + a[...];

        if (sum < x) {
            L...;
        } else if (sum > x) {
            R...;
        } else {
            if (a[L] == a[R]) {
                long long len = ... - ... + 1;
                ans += len * (len - 1) / ...;
                ...;
            } else {
                long long L_cnt = 0, R_cnt = 0;
                long long L_old = a[L];
                long long R_old = a[R];

                while (L <= R && a[L] == ...) {
                    L_cnt...;
                    L...;
                }
                while (L <= R && a[R] == ...) {
                    R_cnt...;
                    R...;
                }
                ans += ... * ...;
            }
        }
    }

    ... << ans << "\n";

    return 0;
}
HIGH (GHEP CAP NAM NU) - HAI CON TRO

Tóm tắt đề bài

Có \(n\) bạn nữ (cân nặng \(a_1, a_2, \dots, a_n\)) và \(m\) bạn nam (cân nặng \(b_1, b_2, \dots, b_m\)).

  • Hai người được ghép đôi nếu độ chênh lệch cân nặng không vượt quá \(k\): \(\vert{}a_i - b_j\vert{} \le k\).
  • Mỗi người chỉ được ghép tối đa với một người khác giới.
  • Tìm số lượng cặp đôi (couple) lớn nhất có thể ghép được.

Hướng giải quyết bằng Hai con trỏ

  1. Sắp xếp cả hai mảng cân nặng \(a\) và \(b\) theo thứ tự tăng dần bằng sort().
  2. Đặt con trỏ \(i = 0\) duyệt danh sách bạn nữ và con trỏ \(j = 0\) duyệt danh sách bạn nam:
    • Nếu \(\vert{}a[i] - b[j]\vert{} \le k\): Hai bạn thỏa mãn ghép cặp \(\rightarrow\) tăng số cặp ans++, đồng thời tăng cả \(i++\) và \(j++\) để xét bạn tiếp theo.
    • Nếu \(a[i] < b[j] - k\): Bạn nữ \(a[i]\) quá nhẹ so với bạn nam \(b[j]\) (và nhẹ hơn tất cả các bạn nam đứng sau), bạn nữ này không thể ghép với ai \(\rightarrow\) bỏ qua bằng cách tăng \(i++\).
    • Nếu \(a[i] > b[j] + k\): Bạn nam \(b[j]\) quá nhẹ so với bạn nữ \(a[i]\) (và nhẹ hơn tất cả các bạn nữ đứng sau), bạn nam này không thể ghép với ai \(\rightarrow\) bỏ qua bằng cách tăng \(j++\).
  3. Dừng lại khi một trong hai danh sách đã duyệt hết (\(i == n\) hoặc \(j == m\)).

Điền vào chỗ trống

C++
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 200005;
long long a[MAXN], b[MAXN];

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

    int n, m;
    long long k;
    ... >> n >> m >> ...;

    for (int i = 0; i < n; i++) cin >> a[...];
    for (int j = 0; j < m; j++) cin >> b[...];

    // Sắp xếp cân nặng hai bên tăng dần
    sort(a, a + ...);
    sort(b, b + ...);

    int i = ...; // Con trỏ bạn nữ
    int j = ...; // Con trỏ bạn nam
    int ans = 0;

    while (i < ... && j < ...) {
        // Kiểm tra điều kiện chênh lệch không quá k
        if (abs(a[i] - b[j]) <= ...) {
            ans...;
            i...;
            j...;
        } else if (a[i] < b[j] - ...) {
            // Nữ quá nhẹ, bỏ qua bạn nữ này
            i...;
        } else {
            // Nam quá nhẹ, bỏ qua bạn nam này
            j...;
        }
    }

    ... << ans << "\n";

    return 0;
}

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.