leetcode 3296. 移山所需的最少秒数 中等

给你一个整数mountainHeight表示山的高度。同时给你一个整数数组workerTimes表示工人们的工作时间单位秒。工人们需要同时进行工作以降低山的高度。对于工人i:山的高度降低x需要花费workerTimes[i] workerTimes[i] * 2 ... workerTimes[i] * x秒。例如山的高度降低 1需要workerTimes[i]秒。山的高度降低 2需要workerTimes[i] workerTimes[i] * 2秒依此类推。返回一个整数表示工人们使山的高度降低到 0 所需的最少秒数。示例 1输入mountainHeight 4, workerTimes [2,1,1]输出3解释将山的高度降低到 0 的一种方式是工人 0 将高度降低 1花费workerTimes[0] 2秒。工人 1 将高度降低 2花费workerTimes[1] workerTimes[1] * 2 3秒。工人 2 将高度降低 1花费workerTimes[2] 1秒。因为工人同时工作所需的最少时间为max(2, 3, 1) 3秒。示例 2输入mountainHeight 10, workerTimes [3,2,2,4]输出12解释工人 0 将高度降低 2花费workerTimes[0] workerTimes[0] * 2 9秒。工人 1 将高度降低 3花费workerTimes[1] workerTimes[1] * 2 workerTimes[1] * 3 12秒。工人 2 将高度降低 3花费workerTimes[2] workerTimes[2] * 2 workerTimes[2] * 3 12秒。工人 3 将高度降低 2花费workerTimes[3] workerTimes[3] * 2 12秒。所需的最少时间为max(9, 12, 12, 12) 12秒。示例 3输入mountainHeight 5, workerTimes [1]输出15解释这个示例中只有一个工人所以答案是workerTimes[0] workerTimes[0] * 2 workerTimes[0] * 3 workerTimes[0] * 4 workerTimes[0] * 5 15秒。提示1 mountainHeight 10^51 workerTimes.length 10^41 workerTimes[i] 10^6分析二分答案。最长的时间是 workerTimes 中最大花费的工人一个人搬山的时间每次二分答案检查中间的时间能否把山搬完。对于一个尝试的答案 mid一个工人能搬的高度为 (sqrt(8LL*mid/workerTimes[i]1LL)-1LL)/2LL即假设可以搬高度为 x则有等差数列workTimeworkTime*2workTime*3···workTime*xmid解出 x 再求和就可以得到时间为 mid 时所有工人可以搬得总高度。class Solution { public: long long minNumberOfSeconds(int mountainHeight, vectorint workerTimes) { int nworkerTimes.size(),maxn0; long long left1,right0x7fffffff,mid0,ans0; for(int i0;in;i) maxnmax(workerTimes[i],maxn); right(1LLmountainHeight)*mountainHeight/2LL*maxn; while(rightleft) { mid(leftright)/2LL; long long height0; for(int i0;in;i) { long long x(sqrt(8LL*mid/workerTimes[i]1LL)-1LL)/2LL; height(1LL*x); } if(height1LL*mountainHeight)ansmid,rightmid-1; else leftmid1; } return ans; } };