Giải bài CP Classes trên ATCoder

Yêu cầu bài toán

Trong lớp học lập trình ABC có $N$ nhóm học. Nhóm thứ $i$ (với $1 \le i \le N$) có tiêu chuẩn tuyển sinh là xếp hạng $A_i$.

Hiện có $Q$ học viên đăng ký. Học viên thứ $j$ (với $1 \le j \le Q$) có xếp hạng $B_j$. Mỗi học viên cảm thấy không hài lòng nếu không phù hợp với nhóm. Độ không hài lòng được tính bằng trị tuyệt đối giữa xếp hạng yêu cầu của nhóm và học viên: $|a - b|$.

Hãy tính giá trị nhỏ nhất của độ không hài lòng cho từng học viên.

[\begin{aligned} 1 \le N \le 300000\ 1 \le Q \le 300000\ 0 \le A_i \le 10^9\ 0 \le B_i \le 10^9\ Dữ liệu đầu vào là số nguyên \end{aligned} ]Phương pháp

Cần sắp xếp mảng xếp hạng lớp học rồi sử dụng tìm kiếm nhị phân để xác định phần tử gần nhất. Hàm lower_bound() trong thư viện <algorithm> rất phù hợp:

// Tìm vị trí chèn phần tử
auto pos = lower_bound(dsLop.begin(), dsLop.end(), xepHangHV);
// Kiểm tra hai phần tử xung quanh
int minUnhappy = min(abs(xepHangHV - *pos), 
                     (pos > dsLop.begin() ? abs(xepHangHV - *(pos-1)) : INF));

Lưu ý xử lý trường hợp con trỏ vượt quá mảng.

Đáp án

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

const int MAXN = 3e5 + 5;
const long long INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, q;
    cin >> n;
    vector<long long> dsLop(n);
    for (auto &x : dsLop) cin >> x;
    
    cin >> q;
    vector<long long> dsHocVien(q);
    for (auto &x : dsHocVien) cin >> x;
    
    sort(dsLop.begin(), dsLop.end());
    
    for (auto xepHang : dsHocVien) {
        auto pos = lower_bound(dsLop.begin(), dsLop.end(), xepHang);
        long long min1 = (pos != dsLop.end() ? abs(*pos - xepHang) : INF);
        long long min2 = (pos != dsLop.begin() ? abs(*(pos-1) - xepHang) : INF);
        cout << min(min1, min2) << '\n';
    }
    
    return 0;
}

1. lower_bound trả về con trỏ trỏ đến phần tử đầu tiên không nhỏ hơn giá trị cần tìm ↩︎