Giải bài ntucoder GIDA - Giao đấu (OLP 2014)

Link bài:

Thuật toán:

• Mục đích ở đây là sắp xếp các cặp đấu sao cho trường sở tại đạt được số điểm lớn nhất.
  
• Sắp xếp lần lượt số điểm năng lực của 2 đội từ thấp đến cao.
  
• Dùng 2 con trỏ, con trỏ i cho trường đề xuất, con trỏ j cho trường sở tại. Ta sẽ tìm các cặp đấu Ai và Bj sao cho Ai < Bj.
  
• Các trường hợp còn lại không cần quan tâm vì thua và hòa sẽ không tính điểm.

Code:

Mã:

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

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

int doit(int ia, int ib){
    if (ia <= n && ib <= n){
        if (a[ia] < b[ib]) return 1 + doit(ia+1, ib+1);
        if (a[ia] >= b[ib]) return doit(ia, ib+1);
    }
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("gida.inp", "r", stdin);
    //freopen("gida.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a;
    for (int i = 1; i <= n; i++) cin >> b;
    sort(a+1, a+1 +n);
    sort(b+1, b+1+n);
    cout << doit(1, 1);

    return 0;
}