leetcode_2300 咒语和药水的成功对数

1. 题意

给定两个数组a、b，对于每个a中的元素输出b中能使$a_i\ast b_j\ge success$
的个数。
咒语和药水成功对数

2. 题解

2.1 二分

将b数组进行排序，找到第一个大于等于
$\lceil \frac{success}{a_i}\rceil$的值，算出其右边还有多少值。

• 代码一

class Solution {
public:

    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success)   {
        int sz = spells.size();
        vector<int> ans(sz, 0);
       
        sort(potions.begin(), potions.end());


        for ( int i = 0; i < sz; ++i ) {
            long long tar = (success + spells[i] - 1) / spells[i];

            int dis = distance(lower_bound(potions.begin(), potions.end(), tar),
                            potions.end());
            
            ans[i] = dis;
        }

       
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 代码二

class Solution {
public:

    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success)   {
        int sz = spells.size();
        vector<int> ans(sz, 0);
       
        sort(potions.begin(), potions.end());


        for ( int i = 0; i < sz; ++i ) {
            long long tar = (success + spells[i] - 1) / spells[i] - 1;

            int dis = distance(upper_bound(potions.begin(), potions.end(), tar),
                            potions.end());
            
            ans[i] = dis;
        }

       
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• mine

class Solution {
public:
    int getSucNum(int zval,const vector<int>& pos, long long target) {

        int lo = 0;
        int hi = pos.size() - 1;

        while (lo <= hi) {
            int mid = (lo + hi) >> 1;

            long long mul = 1LL * zval * pos[mid];
            if ( mul >= target)
                hi = mid - 1;
            else
                lo = mid + 1;
        }

        return pos.size() - lo;
    }

    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success)   {

        int sz = spells.size();
        vector<int> ans( sz, 0);
        sort(potions.begin(), potions.end());

        for (int i = 0; i < sz; ++i) {
            ans[i] = getSucNum(spells[i], potions, success);
        }
        
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

2.2 双指针

将$a$数组进行排序得到下标的顺序$idx$数组，再将$b$数组从大到小进行排序。
当$a[idx[i]]\ast b[j]\ge succcss$时不断移动$j$，算出此时$a[idx[i]]$的药水对数。

• 代码

class Solution {
public:
 

    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success)   {
        int sz = spells.size();
        vector<int> ans(sz, 0);
        vector<int> idx(sz, 0);
        iota(idx.begin(), idx.end(), 0);

        sort(idx.begin(), idx.end(),[&spells](int a, int b)->bool
        {
            return spells[a] < spells[b];
        });
        sort(potions.begin(),potions.end(), greater<int>());

        int j = 0;
        int psz = potions.size();
        for (int i = 0; i < sz; ++i) {
            
            for ( ;j < psz;++j) {
                long long res = 1LL * spells[idx[i]] * potions[j];
                if (res < success)
                    break;
            }
            ans[idx[i]] = j;
        }


       
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33