leetcode875. 爱吃香蕉的珂珂

清疚 2022-09-10 15:16 234阅读 0赞

在这里插入图片描述
思路

二分查找，吃的最大速度是数组中的最大值，吃的最小速度是1，二分法查找符合条件的速度，每次更新最小值

第一眼没看出来是二分查找，还需要练，这个就是暴力，只不过暴力的少了一点。从最小值到最大值的遍历

int isOk(int* piles, int pilesSize, int v, int h)
{

int i = 0;
int count = 0;
for (i = 0; i < pilesSize; i++) { 
    count = count + piles[i] / v;
    if (piles[i] % v) { 
        count ++;
    }
}
return count<=h;

}

int minEatingSpeed(int* piles, int pilesSize, int h)
{ 
    if (pilesSize > h)
        return  -1;
    int i = 0;
    int max = 0;
    for (i = 0; i < pilesSize; i++) { 
        if (max < piles[i]) { 
            max = piles[i];
        }
    }
    int vmin = 1;
    int vmax = max;
    int mid = 0;
    int v = 10000000000;
    while (vmin < vmax) { 
        mid = vmin + (max - vmin) / 2;
        if (isOk(piles, pilesSize, mid, h)) { 
            if (v > mid) { 
                v = mid;
            }
            vmax = mid - 1;
        } else { 
            vmin = mid + 1;
        }
    }
    return v;
}