[475] Heaters

咦，沒有看過這麼慢的版本？！XD

 

至少是自己想的～想法是對的 >< 先貼個初始羞恥版本

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

{

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

}

int findRadius(int* houses, int housesSize, int* heaters, int heatersSize){

int max = INT_MIN;

qsort(houses, housesSize, sizeof(int), comp);

qsort(heaters, heatersSize, sizeof(int), comp);

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

{

int min= INT_MAX;

bool flag=false;

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

{

int diff = abs(houses[i]-heaters[j]);

if (diff < min)

min = diff;

if (flag)

break;

else if (heaters[j]-houses[i]>0)

flag=true;

}

if (min > max)

max = min;

}

return max;

}

奇怪了別人為什麼都寫的出這麼漂亮的版本呢QQ

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

{

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

}

int findRadius(int* houses, int housesSize, int* heaters, int heatersSize){

int max = INT_MIN;

qsort(houses, housesSize, sizeof(int), comp);

qsort(heaters, heatersSize, sizeof(int), comp);

for (int i=0, j=0;i<housesSize;i++)

{

while ((j<heatersSize-1) && (abs(houses[i]-heaters[j]) >= abs(houses[i]-heaters[j+1])))

{

j++;

}

int diff = abs(houses[i]-heaters[j]);

if (diff > max)

max = diff;

}

return max;

}