企业官网建设流程全解析

石家庄+外贸网站建设公司,用c 做的网站怎么打开,定制虚拟偶像app,大学生html网页设计个人博客模板爱吃香蕉的珂珂 问题描述 珂珂喜欢吃香蕉。这里有 n 堆香蕉#xff0c;第 i 堆中有 piles[i] 根香蕉。警卫已经离开了#xff0c;将在 h 小时后回来。 珂珂可以决定她吃香蕉的速度 k#xff08;单位#xff1a;根/小时#xff09;。每个小时#xff0c;她会选择一堆香蕉第i堆中有piles[i]根香蕉。警卫已经离开了将在h小时后回来。珂珂可以决定她吃香蕉的速度k单位根/小时。每个小时她会选择一堆香蕉从中吃掉k根香蕉。如果这堆香蕉少于k根她将吃掉这堆的所有香蕉然后这一小时内不会再吃更多的香蕉。珂珂喜欢慢慢吃但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在h小时内吃掉所有香蕉的最小速度k。示例输入:piles[3,6,7,11],h8输出:4解释:-速度为4时[1,2,2,3]8小时-速度为3时[1,2,3,4]10小时 输入:piles[30,11,23,4,20],h5输出:30解释:每堆需要1小时总共5小时 输入:piles[30,11,23,4,20],h6输出:23算法思路二分搜索搜索范围最小速度1每小时至少吃1根最大速度max(piles)每堆最多需要1小时速度k的范围是[1, max(piles)]单调性如果速度k能在h小时内吃完那么任何速度 k也一定能吃完如果速度k不能在h小时内吃完那么任何速度 k也一定不能吃完时间计算对于速度k吃掉第i堆香蕉需要的时间为ceil(piles[i] / k)总时间 sum(ceil(piles[i] / k)) for all iceil(a/b)可以用(a b - 1) / b计算整数除法搜索策略寻找满足条件的最小k如果time(k) h说明k可行尝试更小的速度right k如果time(k) h说明k太小需要更大的速度left k 1代码实现方法一二分搜索classSolution{/** * 找到珂珂吃香蕉的最小速度 * * param piles 香蕉堆数组 * param h 警卫离开的小时数 * return 最小速度k * * 算法思路 * 1. 确定搜索范围[1, max(piles)] * 2. 使用二分搜索找到满足条件的最小k * 3. 对于每个k计算总耗时 * 4. 根据耗时与h的比较调整搜索范围 */publicintminEatingSpeed(int[]piles,inth){// 找到最大的香蕉堆数量作为搜索上界intmaxPile0;for(intpile:piles){maxPileMath.max(maxPile,pile);}// 二分搜索范围[1, maxPile]intleft1;intrightmaxPile;// 二分搜索寻找最小速度while(leftright){intmidleft(right-left)/2;// 计算以速度mid吃掉所有香蕉需要的总时间longtotalTimecalculateTime(piles,mid);if(totalTimeh){// 当前速度可行尝试更小的速度rightmid;}else{// 当前速度太慢需要更大的速度leftmid1;}}returnleft;}/** * 计算以给定速度吃掉所有香蕉需要的总时间 * * param piles 香蕉堆数组 * param speed 吃香蕉的速度根/小时 * return 总时间小时 * * 使用long防止整数溢出 */privatelongcalculateTime(int[]piles,intspeed){longtotalTime0;for(intpile:piles){// 计算吃掉当前堆需要的时间ceil(pile / speed)// ceil(a/b) (a b - 1) / btotalTime(pile(long)speed-1)/speed;}returntotalTime;}}算法分析时间复杂度O(n log m)n 是香蕉堆的数量m 是最大香蕉堆的数量搜索空间大小二分搜索需要 O(log m) 次迭代每次迭代需要 O(n) 时间计算总耗时空间复杂度O(1)只使用常数额外空间算法过程1piles [3,6,7,11], h 8搜索范围[1, 11]二分搜索过程left1, right11, mid6 - time(6) ceil(3/6)ceil(6/6)ceil(7/6)ceil(11/6) 1122 6 8 - right 6 left1, right6, mid3 - time(3) ceil(3/3)ceil(6/3)ceil(7/3)ceil(11/3) 1234 10 8 - left 4 left4, right6, mid5 - time(5) ceil(3/5)ceil(6/5)ceil(7/5)ceil(11/5) 1223 8 8 - right 5 left4, right5, mid4 - time(4) ceil(3/4)ceil(6/4)ceil(7/4)ceil(11/4) 1223 8 8 - right 4 left4, right4循环结束 返回 4测试用例importjava.util.*;publicclassTest{publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1标准示例int[]piles1{3,6,7,11};inth18;System.out.println(Test 1: solution.minEatingSpeed(piles1,h1));// 4// 测试用例2h等于堆数int[]piles2{30,11,23,4,20};inth25;System.out.println(Test 2: solution.minEatingSpeed(piles2,h2));// 30// 测试用例3h比堆数多1int[]piles3{30,11,23,4,20};inth36;System.out.println(Test 3: solution.minEatingSpeed(piles3,h3));// 23// 测试用例4单堆香蕉int[]piles4{312884470};inth4312884469;System.out.println(Test 4: solution.minEatingSpeed(piles4,h4));// 2// 测试用例5所有堆都是1int[]piles5{1,1,1,1,1};inth55;System.out.println(Test 5: solution.minEatingSpeed(piles5,h5));// 1// 测试用例6h很大int[]piles6{31,26,33,21,40};inth6100;System.out.println(Test 6: solution.minEatingSpeed(piles6,h6));// 1// 测试用例7边界情况 - h等于总香蕉数int[]piles7{1,2,3,4,5};inth715;// 总香蕉数System.out.println(Test 7: solution.minEatingSpeed(piles7,h7));// 1// 测试用例8大数值测试int[]piles8{1000000000};inth82;System.out.println(Test 8: solution.minEatingSpeed(piles8,h8));// 500000000// 测试用例9h刚好等于最优解所需时间int[]piles9{3,6,7,11};inth98;// 刚好是k4所需时间System.out.println(Test 9: solution.minEatingSpeed(piles9,h9));// 4// 测试用例10需要最大速度int[]piles10{10,20,30};inth103;// 每堆1小时System.out.println(Test 10: solution.minEatingSpeed(piles10,h10));// 30}}关键点二分搜索具有单调性速度越大所需时间越少需要找到满足条件的最小值时间计算使用ceil(pile / speed)而不是floor整数除法中ceil(a/b) (a b - 1) / b边界条件处理最小速度为1不能为0最大速度为max(piles)更大的速度没有意义常见问题为什么最大速度是 max(piles)如果速度 max(piles)每堆最多需要1小时更大的速度不会减少总时间因为每堆至少需要1小时为什么不用线性搜索线性搜索时间复杂度 O(n × m)可能超时二分搜索将时间复杂度优化到 O(n log m)