Giải bài ntucoder Khieuvu3 - Khiêu vũ 3

Link bài:

Thuật toán:

• Ta sắp xếp dãy người theo thứ tự tăng dần của chiều cao.
  
• Do không có 2 người nào có chiều cao giống nhau, nên ta sẽ dùng chặt nhị phân để giải quyết bài toán (Giảm thời gian tìm kiếm khi chặt nhị phân chỉ cần O (logn) thay vì duyệt hết dãy với O (n).
  
• Duyệt dãy từ 1 → n. Với người thứ i có chiều cao a, ta sẽ tìm kiếm nhị phân trên dãy i+1→n, vì dãy 1 → i-1 đã tìm kiếm trước đó nên dĩ nhiên sẽ không còn người thỏa mãn.

Code:

Mã:

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

int a[100007], ans, n, pos, k;

bool binary(int l, int r, int todo){
    if (l > r) return false;
    if (a[(l+r)/2] == todo) return true;
    if (a[(l+r)/2] > todo) return binary(l, (l+r)/2 - 1, todo);
    if (a[(l+r)/2] < todo) return binary((l+r)/2 + 1, r, todo);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("kivu3.inp", "r", stdin);
    //freopen("kivu3.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a;
    sort(a+1, a+1+n);
    pos = 1;
    while (pos < n){
        if (binary(pos+1, n, a[pos]+k)) ans++;
        pos++;
    }
    cout << ans;
    
    return 0;
}