题意理解题目问“最长的空题段至少有多长”等价于问是否存在一种抄题方案使得总时间 ≤ t且任意连续空题段长度 ≤ x求这个x的最小值。解题思路a. 二分思想如果空题间隔x过小可能总时间会超过t如果x过大总时间达不到t但不是满足题意条件的最小值。 总时间随着x的增加可能是不上升的可以想到二分。我们写一个二分初始化l-1(不可取到)rn可取。令mid(lr)/2写个check函数如果check(mid)返回True说明x超过了t这时lmid否则rmid。b.check函数实现——单调队列优化DP根据题意在最大空题间隔为x的情况下如果最小的空题方案还大于x那就返回True否则返回False。所以我们要求在最大空题间隔为x的情况下能使总时间最短的空题方案。前i题里面我们记抄了第i题的最短总时间为dp[i]。那么对于i1in我们可以让a[i]min{dp[j]}(i-x-1ji-1)。这里就可以考虑单调队列。在实现上前x1个数有可能i-x-1会下标越界要特判。我们也可以虚拟一个第0题耗时0分钟这个最先入队就可以不用写特判。最后我们的答案会在[n-x,n]之间找最小值。我们也可以虚拟一个第n1题耗时0分钟必做。通过下面的代码可以把最小值转移到dp[n1]上。最后返回dp[n1]t。核心代码boolcheck(intx){dequeintdq;dq.push_back(0);for(inti1;in1;i){while(dq.size()i-dq.front()x1)dq.pop_front();intftdq.front();dp[i]dp[ft]a[i];while(dq.size()dp[i]dp[dq.back()])dq.pop_back();dq.push_back(i);}returndp[n1]t;}AC代码#includebits/stdc.husingnamespacestd;#definelllonglongconstintmaxn5e45;inta[maxn],s,n,t,dp[maxn];boolcheck(intx){dequeintdq;dq.push_back(0);for(inti1;in1;i){while(dq.size()i-dq.front()x1)dq.pop_front();intftdq.front();dp[i]dp[ft]a[i];while(dq.size()dp[i]dp[dq.back()])dq.pop_back();dq.push_back(i);}returndp[n1]t;}intmain(){cinnt;for(inti1;in;i){cina[i];sa[i];}intl-1,rn;while(l1r){intmid(lr)/2;if(check(mid))lmid;elsermid;}coutr;return0;}