烙饼【牛客tracker 每日一题】

烙饼时间限制1 秒空间限制256 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小利同学开了一家网红小吃店专卖烙饼。店里有m mm台烙饼机可以同时工作一台烙饼机同时只能烙一个饼而不同种类的饼烙制时长是不同的。为了节省时间小利同学想出了一种独特的烙饼方法把一张饼分成若干次烙制即一张饼的烙制过程可以是不连续的例如一张饼需要烙8 88分钟可以选择在烙饼机1 11中烙3 33分钟接着取出去烙制别的饼然后再取回该饼继续在任意烙饼机上烙5 55分钟。店里的烙饼机烙制时长只能精确到分钟因此小利只能在每张饼刚好烙制完整数分钟后将其取出。由于是网红店购买订单数量常常爆满于是小利找到你希望你根据n nn个饼的订单信息制定一份包含k kk条烙制记录的烙饼计划使这天完成工作所花费的时间最短当然他也不希望这份计划太繁琐因此在完成上述目标的前提下还应该满足1 ≤ k ≤ 2 × n 1 \le k \le 2 \times n1≤k≤2×n。特殊的小利身手敏捷把饼放入烙饼机与从烙饼机取出饼的时间都可以忽略不计。输入描述给出两个整数n , m ( 1 ≤ n , m ≤ 10 5 ) n, m\ (1 \le n, m \le 10^5)n,m(1≤n,m≤105)分别表示需要制作的饼的数量和烙饼机的数量。下一行为n nn个整数第i ii个整数a i ( 1 ≤ a i ≤ 10 6 ) a_i\ (1 \le a_i \le 10^6)ai​(1≤ai​≤106)表示第i ii号饼需要烙制a i a_iai​分钟。输出描述第一行输出一个整数k kk表示烙制记录数。下面k kk行每行依次输出四个整数i d 1 , i d 2 , l , r id_1, id_2, l, rid1​,id2​,l,r表示第i d 1 id_1id1​号饼在第i d 2 id_2id2​号烙饼机上烙制的时间段为[ l , r ) [l, r)[l,r)。如果存在多种可行结果请输出任意一种。请注意你的输出结果必须同时满足以下所有条件才会返回答案正确1 ≤ k ≤ 2 × n 1 \le k \le 2 \times n1≤k≤2×n1 ≤ i d 1 ≤ n 1 \le id_1 \le n1≤id1​≤n1 ≤ i d 2 ≤ m 1 \le id_2 \le m1≤id2​≤m0 ≤ l r 0 \le l r0≤lr保证所有饼完成烙制同时最后完成工作的烙饼机结束时间最早各饼在一台烙饼机上的烙制时间不能重叠一张饼也不能同时在不同烙饼机上烙制烙制时间段边界处重合是合法的。示例示例 1输入3 2 3 3 5输出3 1 1 0 3 2 1 3 6 3 2 0 5说明第1 11号饼放在1 11号烙饼机烙制时间段为[ 0 , 3 ] [0, 3][0,3]第2 22号饼放在1 11号烙饼机烙制时间段为[ 3 , 6 ] [3, 6][3,6]第3 33号饼放在2 22号烙饼机烙制时间段为[ 0 , 5 ] [0, 5][0,5]。此时1 11号烙饼机最晚结束时间为6 66。可以证明不存在结束时间早于该值的分配方案。示例 2输入3 1 10 3 2输出3 1 1 0 10 2 1 0 3 3 1 3 5数据范围与提示1 ≤ n , m ≤ 10 5 1 \le n, m \le 10^51≤n,m≤1051 ≤ a i ≤ 10 6 1 \le a_i \le 10^61≤ai​≤106饼的烙制过程允许中断即可以在不同时间段、不同烙饼机上分段烙制。每个时间段[ l , r ) [l, r)[l,r)表示左闭右开区间。目标是最小化所有烙饼机中最后结束时间即 makespan。允许抢占式调度时理论最优完成时间为max ⁡ ( max ⁡ i 1 n a i , ⌈ ∑ i 1 n a i m ⌉ ) \max\left(\max_{i1}^{n} a_i,\ \left\lceil \frac{\sum_{i1}^{n} a_i}{m} \right\rceil\right)max(maxi1n​ai​,⌈m∑i1n​ai​​⌉)。输出方案需要满足k ≤ 2 n k \le 2nk≤2n因此需要合理构造避免一张饼被过度拆分。解题思路本题是可抢占式多机调度的构造问题要求将n nn个总时长不同的烙饼分配到m mm台烙饼机上允许同一张饼分段烙制使得所有烙饼机中最后结束时间最早并输出不超过2 n 2n2n条烙制记录。可抢占调度下的理论最短完成时间可直接求得再通过贪心填充构造出合法方案。1. 问题等价转化目标时间下界记所有饼的总时长为S ∑ a i S\sum a_iS∑ai​单张饼最大时长为M max ⁡ a i M\max a_iMmaxai​。在m mm台机器可抢占并行加工时最后结束时间不可能小于T max ⁡ ( M , ⌈ S m ⌉ ) T \max\left(M,\ \left\lceil \frac{S}{m} \right\rceil\right)Tmax(M,⌈mS​⌉)这是因为机器总容量为m T mTmT必须至少容纳S SS同时单张饼无论怎么切分总时长不能超过T TT。可行性该下界在可抢占条件下总是可以达到因此T TT就是最优完成时间。记录数约束输出记录数k ≤ 2 n k \le 2nk≤2n。由于T ≥ M ≥ a i T \ge M \ge a_iT≥M≥ai​每张饼总时长不超过T TT。在贪心填充时饼最多在“当前机器剩余不足”时被切成两段一段放在当前机器末尾另一段放在下一台机器开头。因此每张饼至多产生2 22条记录总记录数不超过2 n 2n2n。2. 算法实现流水线贪心填充计算最优时间读入n , m n,mn,m和所有a i a_iai​。累加总和S SS记录最大值M MM。计算T max ⁡ ( M , ⌈ S / m ⌉ ) T \max(M,\ \lceil S/m \rceil)Tmax(M,⌈S/m⌉)。构造烙制记录初始化当前机器编号id2 1当前机器已安排时间cur 0。按顺序遍历每张饼i ii只要该饼还有剩余时间a[i] 0取take min(T - cur, a[i])即当前机器剩余可安排的时长。记录一条(饼编号 i, 机器编号 id2, 起始时间 cur, 结束时间 cur take)。更新cur take饼剩余a[i] - take。若cur T说明当前机器已满换下一台机器id2 1, cur 0。输出第一行输出记录总数k res.size()。之后每行输出四个整数id1 id2 l r其中id1为饼编号1‑basedid2为机器编号[l, r)为左闭右开时间区间。3. 复杂度分析时间复杂度O ( n k ) O(n k)O(nk)每张饼最多循环两次总记录数k ≤ 2 n k \le 2nk≤2n因此整体为O ( n ) O(n)O(n)。空间复杂度O ( n ) O(n)O(n)存储记录必要开销。总结利用可抢占调度的最优时间公式直接求出最短完成时间T TT。随后按顺序将每张饼依次放入机器遇到机器剩余容量不足就切分到下一台机器同时保证每张饼分段不超过两段满足记录数限制。该方案简单高效适用于n , m ≤ 10 5 n,m \le 10^5n,m≤105的大规模数据。代码简要说明输入处理读入n , m n,mn,m和数组a aa计算总和s u m sumsum和最大值m x mxmx。计算目标时间t max(mx, (sum m - 1) / m)实现上取整。贪心构造用cur跟踪当前机器已用时间cc跟踪机器编号遍历所有饼每次取剩余容量与饼剩余时间的较小值加入记录更新状态。若当前机器满则移动到下一台机器并将cur清零。输出结果先输出记录数然后逐条输出记录注意饼编号加1 11转为 1‑based。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,m,sum,mx;vectorlla;voidsolve(){cinnm;a.resize(n);sum0;mx0;for(autox:a){cinx;sumx;mxmax(mx,x);}ll tmax((ll)mx,(summ-1)/m);ll cur0,cc1;vectortuplell,ll,ll,llres;for(ll i0;in;i){while(a[i]){ll takemin(t-cur,a[i]);res.emplace_back(i,cc,cur,curtake);curtake;a[i]-take;if(curt){cur0;cc;}}}coutres.size();for(auto[id1,id2,l,r]:res)cout\nid11 id2 l r;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}