C++算法：连续时间+多任务并行（二分）

🍗 炸鸡排问题（连续时间并行调度）
一、题目本质

有 n 个任务（鸡排），第 i 个任务需要 t[i] 的总处理时间，同时最多（且必须）处理 k 个任务，任务可随时切换，但完成的任务不能再占用资源
求：最多能持续运行多长时间

👉 本质是：
连续时间 + 必须恰好 k 个并行任务的调度问题

二、关键建模思想

把炸锅看成一个“资源池”：每 1 秒，炸锅消耗 k 单位工作量，第 i 个鸡排最多能提供 t[i] 单位工作量，在 T 秒内，第 i 个鸡排最多贡献min(t[i], T)

三、核心可行性条件（最重要）

炸锅能持续 T 秒 当且仅当：∑min(ai​,T)≥kT

含义解释

左边：所有鸡排在 T 秒内最多能提供的炸制时间

右边：炸锅在 T 秒内必须消耗的炸制时间

四、通用结论（可迁移）

所有：
1.连续时间
2.多任务可切换
3.必须同时运行 k 个任务

都可以尝试：∑min(ai​,T)≥kT进行二分判断

五、题目

PG：炸鸡排

浮点数二分：当答案为浮点数时，二分终止条件不再是left>right，而是用一个较大的二分次数来限制。

intN=100;while(N--){doubleT=(left+right)*1.0/2;// 验证doublecnt=0;for(doubletime:t){cnt+=min(time,T);}if(cnt>=k*T){left=T;}else{right=T;}}

LeetCode：同时运行N台电脑

答案为整型的开区间二分：判断条件为left+1<right，从而保证区间内一定包含整数，否则返回left

longlongmaxRunTime(intn,vector<int>&batteries){longlongleft=0;longlongright=0;for(intt:batteries){right+=t;}right/=n;right+=1;while(left+1<right){longlongmid=(left+right)/2;longlongcnt=0;for(longlongt:batteries){cnt+=min(t,mid);}if(cnt>=mid*n){left=mid;}else{right=mid;}}returnleft;}