Bạn bè độ tuổi phù hợp C++ (Friends Of Appropriate Ages)

Người A KHÔNG gửi lời mời kết bạn B nếu: 1. age[B] ≤ 0.5×age[A] + 7 2. age[B] > age[A] 3. age[B] > 100 && age[A] < 100 Ngược lại A gửi mời B. Tính tổng lời mời (A→B và B→A tính riêng).

Ví dụ

Input - [16,17,18] Output - 2

Giải thích - 17→16, 18→17.

Phương pháp tiếp cận (Bucket + Prefix Sum)

• Bucket[t] = số người tuổi t (tuổi ≤ 120)
• Prefix sum: bucket[i] += bucket[i-1]
• Với mỗi người tuổi x: y = x/2 + 7. Nếu x ≥ y: count += bucket[x] - bucket[y] - 1 (trừ chính mình)

Ví dụ code C++

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

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        vector<int> bucket(1000);
        for (int age : ages) bucket[age]++;
        for (int i = 1; i < 1000; i++) bucket[i] += bucket[i-1];

        int ret = 0;
        for (int age : ages) {
            int x = age, y = age/2 + 7;
            if (x >= y) {
                ret += bucket[x] - bucket[y];
                if (bucket[x] - bucket[y] > 0) ret--;
            }
        }
        return ret;
    }
};

int main() {
    vector<int> v1 = {16, 17, 18};
    Solution ob;
    cout << ob.numFriendRequests(v1);
    return 0;
}

Kết quả

2