[2300] Successful Pairs of Spells and Potions

沒有錯！！！直覺寫法當然是overflow了 QQ

看在這題是藥水跟咒語和哈利波特有點關係，我只好繼續寫下去了QQ

(又不是面試霍格華茲魔法學院QQ) (順便學英文是不QQ)

這個....... binary search 真是讓人頭痛QQ 到底 while 裡面 要不要等於

mid 到底要不要加減一

最後到底是回傳誰XD （抱頭)

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int comp(const void *a, const void *b)

{

return *(int*)a - *(int*)b;

}

int* successfulPairs(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* returnSize) {

int *ret = calloc (spellsSize, sizeof(int));

qsort(potions,potionsSize, sizeof(int), comp );

for (int i=0; i<spellsSize; i++)

{

//binary search potions here

int mid, l=0;

int r=potionsSize-1;

long long product;

if (1.0* spells[i]* potions[r] < success)

{

ret[i]= 0;

continue;

}

while (l<=r)

{

mid = l+(r-l)/2;

product = 1.0* spells[i]* potions[mid];

if (product < success)

l=mid+1;

else //if (product >= success)

r=mid-1;

}

ret[i]= potionsSize - l;

}

*returnSize = spellsSize;

return ret;

}

overflow的寫法XD  （考這麼簡單的話大家也不用刷題刷爆了啊QQ)

int* successfulPairs(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* returnSize) {

int *ret = calloc (spellsSize, sizeof(int));

for (int i=0; i<spellsSize; i++)

{

int count = 0;

for (int j=0; j<potionsSize; j++)

{

if ( (spells[i]* potions[j]) >= success)

count++;

}

ret[i] = count;

}

*returnSize = spellsSize;

return ret;

}