网站是先制作后上线么,新建网站解析域名,gta5此网站正在建设,通州网站建设是什么2021信奥赛C提高组csp-s复赛真题及题解#xff1a;廊桥分配 题目描述 当一架飞机抵达机场时#xff0c;可以停靠在航站楼旁的廊桥#xff0c;也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥#xff0c;因为这样省去了坐摆渡车前往航站楼的周折。然而#x…2021信奥赛C提高组csp-s复赛真题及题解廊桥分配题目描述当一架飞机抵达机场时可以停靠在航站楼旁的廊桥也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥因为这样省去了坐摆渡车前往航站楼的周折。然而因为廊桥的数量有限所以这样的愿望不总是能实现。机场分为国内区和国际区国内航班飞机只能停靠在国内区国际航班飞机只能停靠在国际区。一部分廊桥属于国内区其余的廊桥属于国际区。L 市新建了一座机场一共有n nn个廊桥。该机场决定廊桥的使用遵循“先到先得”的原则即每架飞机抵达后如果相应的区国内/国际还有空闲的廊桥就停靠在廊桥否则停靠在远机位假设远机位的数量充足。该机场只有一条跑道因此不存在两架飞机同时抵达的情况。现给定未来一段时间飞机的抵达、离开时刻请你负责将n nn个廊桥分配给国内区和国际区使停靠廊桥的飞机数量最多。输入格式输入的第一行包含三个正整数n , m 1 , m 2 n, m_1, m_2n,m1​,m2​分别表示廊桥的个数、国内航班飞机的数量、国际航班飞机的数量。接下来m 1 m_1m1​行是国内航班的信息第i ii行包含两个正整数a 1 , i , b 1 , i a_{1, i}, b_{1, i}a1,i​,b1,i​分别表示一架国内航班飞机的抵达、离开时刻。接下来m 2 m_2m2​行是国际航班的信息第i ii行包含两个正整数a 2 , i , b 2 , i a_{2, i}, b_{2, i}a2,i​,b2,i​分别表示一架国际航班飞机的抵达、离开时刻。每行的多个整数由空格分隔。输出格式输出一个正整数表示能够停靠廊桥的飞机数量的最大值。输入输出样例 1输入 13 5 4 1 5 3 8 6 10 9 14 13 18 2 11 4 15 7 17 12 16输出 17输入输出样例 2输入 22 4 6 20 30 40 50 21 22 41 42 1 19 2 18 3 4 5 6 7 8 9 10输出 24说明/提示【样例解释 #1】在图中我们用抵达、离开时刻的数对来代表一架飞机如( 1 , 5 ) (1, 5)(1,5)表示时刻1 11抵达、时刻5 55离开的飞机用√ \surd√表示该飞机停靠在廊桥用× \times×表示该飞机停靠在远机位。我们以表格中阴影部分的计算方式为例说明该表的含义。在这一部分中国际区有2 22个廊桥4 44架国际航班飞机依如下次序抵达首先( 2 , 11 ) (2, 11)(2,11)在时刻2 22抵达停靠在廊桥。然后( 4 , 15 ) (4, 15)(4,15)在时刻4 44抵达停靠在另一个廊桥。接着( 7 , 17 ) (7, 17)(7,17)在时刻7 77抵达这时前2 22架飞机都还没离开、都还占用着廊桥而国际区只有2 22个廊桥所以只能停靠远机位。最后( 12 , 16 ) (12, 16)(12,16)在时刻12 1212抵达这时( 2 , 11 ) (2, 11)(2,11)这架飞机已经离开所以有1 11个空闲的廊桥该飞机可以停靠在廊桥。根据表格中的计算结果当国内区分配2 22个廊桥、国际区分配1 11个廊桥时停靠廊桥的飞机数量最多一共7 77架。【样例解释 #2】当国内区分配2 22个廊桥、国际区分配0 00个廊桥时停靠廊桥的飞机数量最多一共4 44架即所有的国内航班飞机都能停靠在廊桥。需要注意的是本题中廊桥的使用遵循“先到先得”的原则如果国际区只有1 11个廊桥那么将被飞机( 1 , 19 ) (1, 19)(1,19)占用而不会被( 3 , 4 ) (3, 4)(3,4)、( 5 , 6 ) (5, 6)(5,6)、( 7 , 8 ) (7, 8)(7,8)、( 9 , 10 ) (9, 10)(9,10)这4 44架飞机先后使用。【数据范围】对于20 % 20 \%20%的数据n ≤ 100 n \le 100n≤100m 1 m 2 ≤ 100 m_1 m_2 \le 100m1​m2​≤100。对于40 % 40 \%40%的数据n ≤ 5000 n \le 5000n≤5000m 1 m 2 ≤ 5000 m_1 m_2 \le 5000m1​m2​≤5000。对于100 % 100 \%100%的数据1 ≤ n ≤ 10 5 1 \le n \le {10}^51≤n≤105m 1 , m 2 ≥ 1 m_1, m_2 \ge 1m1​,m2​≥1m 1 m 2 ≤ 10 5 m_1 m_2 \le {10}^5m1​m2​≤105所有a 1 , i , b 1 , i , a 2 , i , b 2 , i a_{1, i}, b_{1, i}, a_{2, i}, b_{2, i}a1,i​,b1,i​,a2,i​,b2,i​为数值不超过10 8 {10}^8108的互不相同的正整数且保证对于每个i ∈ [ 1 , m 1 ] i \in [1, m_1]i∈[1,m1​]都有a 1 , i b 1 , i a_{1, i} b_{1, i}a1,i​b1,i​以及对于每个i ∈ [ 1 , m 2 ] i \in [1, m_2]i∈[1,m2​]都有a 2 , i b 2 , i a_{2, i} b_{2, i}a2,i​b2,i​。思路分析核心思路这是一个区间分配优化问题核心是给国内和国际区域分配固定数量的廊桥使得停靠廊桥的飞机总数最大化。关键观察每个区域的飞机停靠是独立的在每个区域内飞机按到达时间顺序依次分配廊桥廊桥分配遵循先到先得原则有空闲廊桥就分配否则飞机去远机位算法设计主要步骤预处理对每个区域的航班按到达时间排序计算前缀和对于每个区域计算当分配 k 个廊桥时能停靠的飞机数量组合优化枚举分配给国内区的廊桥数 i国际区得到 n-i 个求和取最大值技术细节使用优先队列小根堆维护廊桥的可用时间模拟廊桥分配过程记录每个廊桥编号的使用情况通过一次模拟得到所有可能的 k 值对应的答案时间复杂度分析排序O(m log m)m 是航班总数模拟分配O(m log n)使用优先队列总体O(m log m)可以处理 10^5 的数据规模代码实现#includebits/stdc.husingnamespacestd;constintN100010;// 飞机信息到达时间、离开时间structPlane{inta,b;};// 比较函数按到达时间排序boolcmp(Plane x,Plane y){returnx.ay.a;}// 计算一个区域分配不同数量廊桥时的收益voidcalc(intm,Plane p[],intf[]){// 按到达时间排序sort(p1,pm1,cmp);// 两个优先队列// idle: 空闲廊桥编号小根堆// busy: 正在使用的廊桥离开时间编号小根堆priority_queueint,vectorint,greaterintidle;priority_queuepairint,int,vectorpairint,int,greaterpairint,intbusy;// 初始化所有廊桥都空闲这里假设有足够多最后只取前N个for(inti1;iN;i){idle.push(i);}// 模拟飞机依次到达for(inti1;im;i){intarrivep[i].a;intdepartp[i].b;// 释放已经离开的廊桥while(!busy.empty()busy.top().firstarrive){intbridgebusy.top().second;busy.pop();idle.push(bridge);}// 如果有空闲廊桥分配一个if(!idle.empty()){intbridgeidle.top();idle.pop();busy.push({depart,bridge});// 记录这个廊桥的使用次数用于计算前缀和if(bridgeN){f[bridge];}}}// 计算前缀和f[i]表示分配i个廊桥能停靠的飞机数for(inti1;iN;i){f[i]f[i-1];}}intn,m1,m2;Plane p1[N],p2[N];// 国内和国际航班intf1[N],f2[N];// 前缀和数组intmain(){// 读取输入cinnm1m2;for(inti1;im1;i){cinp1[i].ap1[i].b;}for(inti1;im2;i){cinp2[i].ap2[i].b;}// 计算两个区域的前缀和calc(m1,p1,f1);calc(m2,p2,f2);// 枚举分配给国内区的廊桥数取最大值intans0;for(inti0;in;i){intjn-i;// 国际区得到的廊桥数// 注意不能超过实际航班数intcurf1[min(i,m1)]f2[min(j,m2)];ansmax(ans,cur);}coutansendl;return0;}功能分析1. 数据结构设计Plane结构体存储航班的到达和离开时间f1[], f2[]前缀和数组f[k]表示分配 k 个廊桥时能停靠的飞机数优先队列idle维护空闲廊桥编号优先队列busy维护正在使用的廊桥按离开时间排序2. 核心函数calc输入m: 航班数量p[]: 航班数组f[]: 结果前缀和数组流程排序按到达时间升序排列航班初始化所有廊桥编号 1~N 放入空闲队列模拟分配对于每个航班先释放离开时间早于当前到达时间的廊桥如果有空闲廊桥分配编号最小的廊桥记录使用次数前缀和将廊桥使用次数转换为前缀和形式3. 主流程读取航班信息分别计算国内和国际区域的廊桥收益枚举分配方案取最大值4. 关键优化点一次模拟得到所有 k 值的结果通过记录每个廊桥的使用次数可以知道分配 i 个廊桥时能停靠多少飞机贪心分配廊桥总是分配编号最小的空闲廊桥这保证了廊桥的充分利用优先队列高效维护O(log n) 时间复杂度完成廊桥的分配和释放复杂度分析时间复杂度排序O(m log m)m m1 m2模拟分配O(m log n)每个航班一次优先队列操作枚举分配方案O(n)总体O(m log m)满足题目要求空间复杂度O(m n)存储航班信息和前缀和数组专栏推荐信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}