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

Link bài:

Thuật toán:

• Gọi dãy các bạn trai là A và các bạn nữ là B.
  
• Ta sắp xếp các bạn nam và nữ theo thứ tự tăng dần về chiều cao.
  
• Bài này ta sẽ dùng 2 con trỏ. Với cặp A (i) và B (j) thỏa mãn ta sẽ ưu tiên dịch chuyển con trỏ trên dãy A một lượng x đơn vị đến khi gặp A (i+x) > B (j+1). Mỗi cặp tương ứng như vậy sẽ tăng kết quả lên 1.

Code:

Mã:

#include <bits/stdc++.h>
#define repinc(k, n) for (int i = k; i <= n; i++)
using namespace std;

int n, m;
int a[100007], b[100007];

void read(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("KIVU.INP", "r", stdin);
    //freopen("KIVU.OUT", "w", stdout);
    cin >> n >> m;
    repinc(1, n) cin >> a;
    repinc(1, m) cin >> b;
}

void run(){
    sort(a+1, a+n+1);
    sort(b+1, b+m+1);
    int apin = 1;
    int bpin = 1;
    int ans = 0;
    while (apin <= n && bpin <= m){
        if (a[apin] > b[bpin]){
            ans++;
            apin++;
            bpin++;
        } else {
            apin++;
        }
    }
    cout << ans;
}

int main(){
    read();
    run();

    return 0;
}