企业官网建设流程全解析

基于ssh框架的网站开发流程图,wordpress插件入门,网络规划建设方案,网页布局设计主要有什么类型问题描述 一个大城市有一个年客流量 400040004000 万的国际机场#xff0c;但该机场以世界上最为拥堵的机场之一而臭名昭著。在这个机场#xff0c;只有一条跑道。因此#xff0c;跑道上总是挤满了等待起飞的飞机。有两条路可以接近跑道#xff0c;分别称为西路 WWW 和东路…问题描述一个大城市有一个年客流量400040004000万的国际机场但该机场以世界上最为拥堵的机场之一而臭名昭著。在这个机场只有一条跑道。因此跑道上总是挤满了等待起飞的飞机。有两条路可以接近跑道分别称为西路WWW和东路EEE。飞机在这两条路上等待起飞。在每个时刻ttt任意数量的飞机到达西路WWW和东路EEE。每个在时刻ttt到达WWW或EEE的飞机会获得一个等级该等级等于同一条路上排在它前面的等待飞机的数量。然后控制塔会选择WWW或EEE之一让该路上最前面的飞机起飞。给定飞机到达时刻的信息我们关注控制塔的起飞调度方案以使所有飞机的最大等级最小化。输入格式输入包含TTT个测试用例。测试用例的数量TTT在输入的第一行给出。每个测试用例的第一行包含一个整数nnn(1≤n≤5000)(1 \leq n \leq 5000)(1≤n≤5000)表示时刻的数量。在每个测试用例接下来的nnn行中第iii行包含两个整数aia_iai​和bib_ibi​分别表示时刻iii到达西路WWW和东路EEE的飞机数量其中0≤ai,bi≤200 \leq a_i, b_i \leq 200≤ai​,bi​≤20。输出格式为每个测试用例输出一行包含所有可能起飞调度方案中最大等级的最小值。题目分析这是一个经典的调度优化问题我们需要在满足每时刻只能起飞一架飞机的约束下最小化所有飞机在所有时刻出现的最大等待等级。问题转化首先理解等级的计算方式一架飞机在时刻ttt到达时它的等级等于同一条路上排在它前面的飞机数量。注意这个等级是在到达时刻计算的之后如果前面的飞机起飞了这架飞机的等级会减小但我们关心的是所有飞机在所有时刻曾经达到过的最大等级。设totalW[i]totalW[i]totalW[i]表示到时刻iii为止西路WWW累计到达的飞机总数totalE[i]totalE[i]totalE[i]表示到时刻iii为止东路EEE累计到达的飞机总数takeW[i]takeW[i]takeW[i]表示到时刻iii为止从西路WWW起飞的飞机总数takeE[i]takeE[i]takeE[i]表示到时刻iii为止从东路EEE起飞的飞机总数由于每时刻只能起飞一架飞机我们有takeW[i]takeE[i]i takeW[i] takeE[i] itakeW[i]takeE[i]i在时刻iii西路WWW上等待的飞机数为waitW[i]totalW[i]−takeW[i] waitW[i] totalW[i] - takeW[i]waitW[i]totalW[i]−takeW[i]东路EEE上等待的飞机数为waitE[i]totalE[i]−takeE[i] waitE[i] totalE[i] - takeE[i]waitE[i]totalE[i]−takeE[i]在时刻iii新到达的飞机中最后到达的那架飞机即等级最高的的等级为西路waitW[i−1]a[i]−1waitW[i-1] a[i] - 1waitW[i−1]a[i]−1东路waitE[i−1]b[i]−1waitE[i-1] b[i] - 1waitE[i−1]b[i]−1这里waitW[i−1]waitW[i-1]waitW[i−1]表示时刻iii之前已经在等待的飞机数a[i]−1a[i]-1a[i]−1表示在同一时刻到达但排在前面的飞机数。我们的目标是找到一种调度方案使得max⁡i(max⁡(waitW[i−1]a[i]−1, waitE[i−1]b[i]−1)) \max_{i} \left( \max(waitW[i-1] a[i] - 1, \ waitE[i-1] b[i] - 1) \right)imax​(max(waitW[i−1]a[i]−1,waitE[i−1]b[i]−1))最小化。关键观察注意到waitW[i]totalW[i]−takeW[i]waitW[i] totalW[i] - takeW[i]waitW[i]totalW[i]−takeW[i]且takeW[i]takeE[i]itakeW[i] takeE[i] itakeW[i]takeE[i]i所以waitE[i]totalE[i]−(i−takeW[i])waitE[i] totalE[i] - (i - takeW[i])waitE[i]totalE[i]−(i−takeW[i])。设最大等待飞机数的上限为midmidmid注意最大等级 最大等待数 -111那么我们需要保证在任意时刻iiiwaitW[i]totalW[i]−takeW[i]≤midwaitW[i] totalW[i] - takeW[i] \leq midwaitW[i]totalW[i]−takeW[i]≤midwaitE[i]totalE[i]−(i−takeW[i])≤midwaitE[i] totalE[i] - (i - takeW[i]) \leq midwaitE[i]totalE[i]−(i−takeW[i])≤mid这两个不等式可以转化为对takeW[i]takeW[i]takeW[i]的约束takeW[i]≥totalW[i]−midtakeW[i] \geq totalW[i] - midtakeW[i]≥totalW[i]−midtakeW[i]≤totalE[i]−miditakeW[i] \leq totalE[i] - mid itakeW[i]≤totalE[i]−midi此外还有基本约束takeW[i]≥0takeW[i] \geq 0takeW[i]≥0takeW[i]≤totalW[i]takeW[i] \leq totalW[i]takeW[i]≤totalW[i]不能起飞超过已到达的飞机数takeW[i]≤itakeW[i] \leq itakeW[i]≤i起飞总数不能超过时刻数i−takeW[i]≤totalE[i]i - takeW[i] \leq totalE[i]i−takeW[i]≤totalE[i]东路起飞数不能超过东路到达数解题思路二分答案由于答案具有单调性如果最大等级kkk可行那么k1k1k1也一定可行我们可以使用二分查找来寻找最小的可行最大等级。对于给定的midmidmid我们需要判断是否存在一个调度方案使得所有时刻的等待飞机数都不超过midmidmid。贪心验证验证函数check(mid)的核心思想是维护takeWtakeWtakeW的可能取值范围[L,R][L, R][L,R]然后逐时刻更新这个范围。初始化L0, R0L 0, \ R 0L0,R0第000时刻未起飞任何飞机对于每个时刻iii更新累计到达飞机数totalWa[i], totalEb[i]totalW a[i], \ totalE b[i]totalWa[i],totalEb[i]由于必须起飞一架飞机takeWtakeWtakeW最多可以增加111RR1R R 1RR1应用基本约束Rmin⁡(R, totalW)R \min(R, \ totalW)Rmin(R,totalW)不能起飞超过已到达的飞机数应用等待数约束从不等式takeW≥totalW−midtakeW \geq totalW - midtakeW≥totalW−mid得Lmax⁡(L, totalW−mid)L \max(L, \ totalW - mid)Lmax(L,totalW−mid)从不等式takeW≤totalE−miditakeW \leq totalE - mid itakeW≤totalE−midi得Rmin⁡(R, totalE−midi)R \min(R, \ totalE - mid i)Rmin(R,totalE−midi)应用其他边界约束Lmax⁡(L, 0)L \max(L, \ 0)Lmax(L,0)Lmax⁡(L, i−totalE)L \max(L, \ i - totalE)Lmax(L,i−totalE)确保takeEi−takeW≤totalEtakeE i - takeW \leq totalEtakeEi−takeW≤totalERmin⁡(R, i)R \min(R, \ i)Rmin(R,i)Rmin⁡(R, totalW)R \min(R, \ totalW)Rmin(R,totalW)如果LRL RLR则当前midmidmid不可行如果处理完所有时刻后L≤RL \leq RL≤R则midmidmid可行。算法复杂度二分查找O(log⁡M)O(\log M)O(logM)其中MMM是飞机总数的上界最大为5000×20×22000005000 \times 20 \times 2 2000005000×20×2200000每次验证O(n)O(n)O(n)n≤5000n \leq 5000n≤5000总复杂度O(T×n×log⁡M)O(T \times n \times \log M)O(T×n×logM)在题目限制下完全可行代码实现// Airport// UVa ID: 1450// Verdict: Accepted// Submission Date: 2025-12-16// UVa Run Time: 0.010s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintN5005;intt,n,a[N],b[N];// 检查最大等待数不超过 mid 是否可行boolcheck(intmid){intan0,bn0,have0;// an: W路累计等待数, bn: E路累计等待数, have: 可用起飞时隙for(inti0;in;i){ana[i];// 更新W路累计等待数bnb[i];// 更新E路累计等待数// 计算至少需要从各条路起飞的飞机数intneedamax(an-mid,0);intneedbmax(bn-mid,0);// 如果需要的起飞数超过可用时隙则不可行if(needaneedbhave)returnfalse;// 更新可用起飞时隙和等待数if(an0bn0)bn--;// 只能从E路起飞elseif(bn0an0)an--;// 只能从W路起飞elseif(an0bn0anbnhave)have;// 两条路都有飞机增加起飞机会}returntrue;}// 二分查找最小可行最大等待数intsolve(){intleft0,right100000;// 等待数上界while(leftright){intmid(leftright)/2;if(check(mid))rightmid;elseleftmid1;}// 最大等级 最大等待数 - 1returnleft0?0:left-1;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cint;while(t--){cinn;for(inti0;in;i)cina[i]b[i];coutsolve()\n;}return0;}代码解析输入处理使用cin读取输入关闭同步以提高效率。验证函数check(mid)实现上述贪心验证逻辑。an和bn分别记录两条路的累计等待飞机数have记录可用的起飞时隙数即已过去的时间needa和needb分别表示为了保持等待数不超过midmidmid至少需要从各条路起飞的飞机数二分查找在范围[0,100000][0, 100000][0,100000]内查找最小可行最大等待数。输出处理注意最大等级 最大等待数 - 1 所以最终答案为left - 1。样例分析样例输入3 1 1 1 3 3 2 0 3 2 0 6 0 1 1 1 1 2 1 1 1 1 6 0样例输出0 3 5解释第一个测试用例只有111个时刻两条路各到达111架飞机。最优调度是立即从任意一条路起飞一架飞机最大等级为000。第二个测试用例需要仔细调度才能得到最大等级333如题目中的示例所示。第三个测试用例通过合理调度可以使得最大等级为555。总结本题的关键在于将问题转化为对最大等待飞机数的约束然后使用二分答案和贪心验证的方法求解。贪心验证的核心是维护takeWtakeWtakeW的可能取值范围通过逐时刻更新约束条件来判断可行性。这种解法既高效又易于实现能够处理题目中的最大数据规模。算法的时间复杂度为O(T×n×log⁡M)O(T \times n \times \log M)O(T×n×logM)空间复杂度为O(n)O(n)O(n)完全满足题目要求。