题解：洛谷 AT_abc463_c [ABC463C] Tallest at the Moment

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷AT_abc463_c [ABC463C] Tallest at the Moment - 洛谷【题目描述】Currently, there areN NNTakahashi in a conference room. Thei ii-th( 1 ≤ i ≤ N ) (1\le i\le N)(1≤i≤N)Takahashi has a height ofH i H _ iHi​and will leave the roomL i L _ iLi​minutes from now. Once a Takahashi leaves the room, he never returns.You are givenQ QQqueries, so answer them in order. For thei ii-th( 1 ≤ i ≤ Q ) (1\le i\le Q)(1≤i≤Q)query, you are given an integerT i T _ iTi​, so find the maximum height among the Takahashi who are in the roomT i 1 2 T _ i\dfrac12Ti​21​minutes from now. Under the constraints of this problem, it is guaranteed that at least one Takahashi will be in the roomT i 1 2 T _ i\dfrac12Ti​21​minutes from now.当前会议室里有N NN个高橋。第i ii个( 1 ≤ i ≤ N ) (1\le i\le N)(1≤i≤N)高橋的身高为H i H_iHi​他将在L i L_iLi​分钟后离开房间。一旦高橋离开房间他就不会再回来。给定Q QQ个查询请按顺序回答。对于第i ii个( 1 ≤ i ≤ Q ) (1\le i\le Q)(1≤i≤Q)查询给定一个整数T i T_iTi​请找出T i 1 2 T_i\dfrac12Ti​21​分钟后仍在房间里的高橋中的最大身高。在本题的约束条件下保证T i 1 2 T_i\dfrac12Ti​21​分钟后房间里至少还有一个高橋。【输入】The input is given from Standard Input in the following format:N NNH 1 H _ 1H1​L 1 L _ 1L1​H 2 H _ 2H2​L 2 L _ 2L2​⋮ \vdots⋮H N H _ NHN​L N L _ NLN​Q QQT 1 T _ 1T1​T 2 T _ 2T2​… \ldots…T Q T _ QTQ​【输出】OutputQ QQlines. Thei ii-th line( 1 ≤ i ≤ Q ) (1\le i\le Q)(1≤i≤Q)should contain the answer to thei ii-th query.【输入样例】4 31 4 26 5 3 5 15 9 4 3 4 5 6【输出样例】31 26 15 15【算法标签】#普及- #整数二分【代码详解】#includebits/stdc.husingnamespacestd;constintN300005;// 最大节点数量intn,q;// n: 高橋数量, q: 查询数量intmaxH[N];// 后缀最大值数组maxH[i] 表示从第 i 个到第 n 个高橋中的最大身高structNode{inth,l;// h: 身高, l: 离开时间}a[N];// 存储所有高橋的信息// 按离开时间升序排序若离开时间相同则按身高升序boolcmp(Node x,Node y){if(x.l!y.l)returnx.ly.l;returnx.hy.h;}// 二分查找判断第 mid 个高橋的离开时间是否 x即 T_i0.5 分钟后是否仍在房间boolcheck(intx,intmid){if(a[mid].lx)returntrue;// 仍在房间elsereturnfalse;// 已离开}// 二分查找找到第一个离开时间 x 的高橋的位置intfind(intx){intl1,rn;while(lr){intmid(lr)/2;if(check(x,mid))rmid;// 第 mid 个仍在房间答案在左半部分elselmid1;// 第 mid 个已离开答案在右半部分}returnl;}intmain(){cinn;// 读入高橋数量for(inti1;in;i)cina[i].ha[i].l;// 读入每个高橋的身高和离开时间sort(a1,an1,cmp);// 按离开时间升序排序// 预处理后缀最大值从后往前遍历maxH[i] max(a[i..n].h)for(intin;i1;i--)maxH[i]max(maxH[i1],a[i].h);cinq;// 读入查询数量while(q--)// 依次处理每个查询{intt;cint;tround(t0.5);// 计算 T_i 0.5 的整数表示等价于向上取整intposfind(t);// 二分查找第一个离开时间 t 的位置// cout t pos t pos endl;coutmaxH[pos]endl;// 输出从 pos 开始到末尾的所有高橋中的最大身高}return0;}【运行结果】4 31 4 26 5 3 5 15 9 4 3 4 5 6 31 26 15 15