I. chino with mates

古城微笑少年丶 2022-10-13 12:42 154阅读 0赞

## 题目大意 ##

blind date event – 相亲

n n n 名男性，  m m m 名女性

男性的个性值为 a i a\_i ai， 女性的个性值为 b j b\_j bj ，当 a i ∗ b i 在 \[ L ， R \] a\_i \* b\_i在 \[L， R\] ai∗bi在\[L，R\] 这个范围就算配对合格。

求有多少对？

--------------------

## 题解 ##

lower\_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper\_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

注意边界即可

--------------------

## 代码 ##

#include <bits/stdc++.h>
    #define rep(i,l,r) for(int i=l;i<=r;i++)
    #define all(a) (a).begin(),(a).end()
    #define pb push_back
    using namespace std;
    typedef long long ll;
    typedef vector<int> vi;
    
    ll ans;
    int n,m,tmp,l,r;
    
    int main() { 
        cin >> n >> m; 
        vi a,b;
        rep(i,1,n) cin >> tmp, a.pb(tmp);
        rep(i,1,m) cin >> tmp, b.pb(tmp);
    
        cin >> l >> r;
        
        sort(all(a)); 
        sort(all(b));
    
        for (auto &x : a)
        { 
            if (x < 0)
                ans += upper_bound(all(b), floor((double)l / x)) - lower_bound(all(b), ceil(double(r) / x));
            else if (x > 0)
                ans += upper_bound(all(b), floor((double)r / x)) - lower_bound(all(b), ceil(double(l) / x));
            else if (l <= 0 && r >= 0) ans += m;
        }
    
        cout << ans;
        
        return 0;
    }

--------------------