Re: [閒聊] 每日LeetCode

[oin1104 (是oin的說)]

https://leetcode.com/problems/successful-pairs-of-spells-and-potions/

今天的做過惹

來做個別的

題目：
給你一串spells跟potions 還有success

問你某個spells乘上全部potions
會大於success的有幾個

舉例比較好說明= =

舉例：
spells 是 3,1,2
potions 是 1,2,3,4,5
success 是 10

這樣對於spells的3來說
乘起來會變 3,6,9,12,15
12 15超過success  所以有兩個

對spells的1
乘起來會變 1,2,3,4,5
一個都沒有

對spells的2
乘起來會變 2,4,6,8,10
10剛好 所以有一個



解法：

對每個spells[i]去對potions二分搜

然後就好了

對ㄚ

二份搜真的很靠北

不管是手刻還是用他的函式

都要知道他什麼時候停下來要拿什麼東西

很煩





```cpp
class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long
long success)
    {
        sort(potions.begin() , potions.end() , less<int>() );

        // for(int k : potions)
        // {
        //     printf("%d ",k);
        // }
        // printf("\n============\n");

        int len = spells.size();
        int lenp = potions.size();
        vector<int> res(len , 0);

        for(int si = 0 ; si < len ; si ++)
        {

            int l = 0;
            int r = lenp-1;
            int m = 0 ;
            while(l <= r)
            {
                m = (l+r)/2 ;
                long long ress = ((long long)potions[m] * (long long)spells[si])
;
                // printf("%d = %d * %d , l:%d r:%d \n",ress,potions[m],spells[s
i],l,r);
                if(ress < success)
                {
                    l = m+1;
                }
                else if (ress >= success)
                {
                    r = m-1;
                }
            }
            // printf("l:%d r:%d\n",l,r);
            // printf("============\n");
            res[si] = (lenp) - l;

        }

        return res;
    }
};
```



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.50.234 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707391027.A.B27.html
推 digua: 大師
→ Apache: 你用Python刷 有built-in
→ oin1104: 然後回傳每個的陣列 所以是[2,0,1]
→ oin1104: 我記得cpp也有內建函式 但是我想刻刻看
→ Apache: C++20才有
→ oin1104: :O
推 SecondRun: 大師
推 DJYOSHITAKA: 大師