河南省网站建设哪家好库尔勒网站建设

河南省网站建设哪家好,库尔勒网站建设,优秀网络广告文案案例,素马网站建设费用差距题目描述 河上有 nnn 座桥#xff0c;每座桥有一个高度 hih_ihi​ 。河水会泛滥 mmm 次#xff0c;每次洪水会将水位从上次洪水结束后的高度 bi−1b_{i-1}bi−1​ 上升到 aia_iai​ #xff0c;然后回落到 bib_ibi​ 。初始水位为 111 。 题目规定#xff1a;如果一座桥在洪…题目描述河上有nnn座桥每座桥有一个高度hih_ihi​。河水会泛滥mmm次每次洪水会将水位从上次洪水结束后的高度bi−1b_{i-1}bi−1​上升到aia_iai​然后回落到bib_ibi​。初始水位为111。题目规定如果一座桥在洪水结束后仍然在水下即水位不低于桥的高度那么下次洪水时它不会被视为再次被淹。也就是说每次洪水只记录上升阶段水位从bi−1b_{i-1}bi−1​上升到aia_iai​期间被淹的桥。给定nnn座桥的高度和mmm次洪水的数据求有多少座桥至少被淹了kkk次。输入格式输入最多包含252525个测试用例。每个测试用例的第一行包含三个整数n,m,kn, m, kn,m,k1≤n,m,k≤1051 \leq n, m, k \leq 10^51≤n,m,k≤105。第二行包含nnn个整数hih_ihi​表示每座桥的高度2≤hi≤1082 \leq h_i \leq 10^82≤hi​≤108。接下来的mmm行每行包含两个整数aia_iai​和bib_ibi​1≤biai≤108,aibi−11 \leq b_i a_i \leq 10^8, a_i b_{i-1}1≤bi​ai​≤108,ai​bi−1​。整个输入的文件大小不超过5MB5\text{MB}5MB。输出格式对于每个测试用例输出至少被淹了kkk次的桥的数量。题目分析核心逻辑对于第iii次洪水洪水开始前的水位是bi−1b_{i-1}bi−1​第一次洪水前b01b_0 1b0​1水位上升到aia_iai​然后回落到bib_ibi​桥被淹的条件在上升阶段水位超过了桥的高度即bi−1h≤aib_{i-1} h \leq a_ibi−1​h≤ai​。为什么不是bib_ibi​因为下降阶段不影响本次是否被淹的记录只影响下次洪水是否算作“再次被淹”。关键点只考虑上升阶段题目描述中的文字游戏关键就在于下降阶段不影响计数只影响下次判断。区间更新对于每次洪水需要给所有高度在(bi−1,ai](b_{i-1}, a_i](bi−1​,ai​]范围内的桥的计数111。高效处理直接遍历每座桥更新会超时O(nm)O(nm)O(nm)需要使用差分技巧。算法步骤将桥的高度排序以便二分查找。使用差分数组记录每座桥被淹的次数。遍历每次洪水用二分查找找到高度bi−1 b_{i-1}bi−1​的第一个桥的索引leftleftleft用二分查找找到高度≤ai\leq a_i≤ai​的最后一个桥的索引rightrightright如果left≤rightleft \leq rightleft≤right则在差分数组中标记区间[left,right][left, right][left,right]加111通过差分数组前缀和计算每座桥的实际被淹次数。统计次数≥k\geq k≥k的桥的数量。时间复杂度排序桥高度O(nlog⁡n)O(n \log n)O(nlogn)每次洪水二分查找O(log⁡n)O(\log n)O(logn)总O(mlog⁡n)O(m \log n)O(mlogn)前缀和统计O(n)O(n)O(n)总复杂度O((nm)log⁡n)O((nm) \log n)O((nm)logn)可以处理10510^5105的数据规模。空间复杂度存储桥高度和差分数组O(n)O(n)O(n)代码实现// High Bridge Low Bridge// UVa ID: 12663// Verdict: Accepted// Submission Date: 2025-12-23// UVa Run Time: 0.040s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN100010;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcaseNo1;intn,m,k;intbridgeHeight[MAXN],diff[MAXN];inta,b;while(cinnmk){for(inti0;in;i){cinbridgeHeight[i];diff[i]0;}sort(bridgeHeight,bridgeHeightn);intlastWaterLevel1;// 初始水位为1也是第一次洪水前的b₀for(inti0;im;i){cinab;// 本次洪水影响高度在 (lastWaterLevel, a] 范围内的桥// 使用 upper_bound 找到第一个 lastWaterLevel 的桥// 使用 upper_bound 找到第一个 a 的桥然后-1得到最后一个 ≤ a 的桥intleftupper_bound(bridgeHeight,bridgeHeightn,lastWaterLevel)-bridgeHeight;intrightupper_bound(bridgeHeight,bridgeHeightn,a)-bridgeHeight-1;if(leftright){diff[left];diff[right1]--;}lastWaterLevelb;// 更新为本次洪水结束后的水位}// 计算每座桥被淹的次数intcurrentFloodCount0;intanswer0;for(inti0;in;i){currentFloodCountdiff[i];if(currentFloodCountk)answer;}coutCase caseNo: answer\n;}return0;}样例解释样例111输入 2 2 2 2 5 6 2 8 3桥高度2,52, 52,5第111次洪水影响(1,6](1, 6](1,6]→ 桥2,52, 52,5各111第222次洪水影响(2,8](2, 8](2,8]→ 桥555111桥222高度为222不在(2,8](2,8](2,8]区间统计桥222被淹111次桥555被淹222次输出111只有桥555被淹≥2\geq 2≥2次样例222输入 5 3 2 2 3 4 5 6 5 3 4 2 5 2桥高度2,3,4,5,62, 3, 4, 5, 62,3,4,5,6第111次洪水影响(1,5](1, 5](1,5]→ 桥2,3,4,52,3,4,52,3,4,5各111第222次洪水影响(3,4](3, 4](3,4]→ 桥444111第333次洪水影响(2,5](2, 5](2,5]→ 桥3,4,53,4,53,4,5各111统计桥2:12:12:1次桥3:23:23:2次桥4:34:34:3次桥5:25:25:2次桥6:06:06:0次输出333桥3,4,53,4,53,4,5被淹≥2\geq 2≥2次总结本题的关键在于理解题目描述中的文字游戏每次洪水只记录上升阶段被淹的桥下降阶段只影响下次是否算作“再次被淹”。通过将桥高度排序并使用差分技巧可以高效地处理区间更新问题。注意数据范围较大需要使用O((nm)log⁡n)O((nm) \log n)O((nm)logn)的算法才能通过。