题解：洛谷 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 NN
H 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 QQ
T 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

【算法标签】

#普及- #整数二分

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=300005;// 最大节点数量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.l<y.l;returnx.h<y.h;}// 二分查找判断：第 mid 个高橋的离开时间是否 >= x（即 T_i+0.5 分钟后是否仍在房间）boolcheck(intx,intmid){if(a[mid].l>=x)returntrue;// 仍在房间elsereturnfalse;// 已离开}// 二分查找：找到第一个离开时间 >= x 的高橋的位置intfind(intx){intl=1,r=n;while(l<r){intmid=(l+r)/2;if(check(x,mid))r=mid;// 第 mid 个仍在房间，答案在左半部分elsel=mid+1;// 第 mid 个已离开，答案在右半部分}returnl;}intmain(){cin>>n;// 读入高橋数量for(inti=1;i<=n;i++)cin>>a[i].h>>a[i].l;// 读入每个高橋的身高和离开时间sort(a+1,a+n+1,cmp);// 按离开时间升序排序// 预处理后缀最大值：从后往前遍历，maxH[i] = max(a[i..n].h)for(inti=n;i>=1;i--)maxH[i]=max(maxH[i+1],a[i].h);cin>>q;// 读入查询数量while(q--)// 依次处理每个查询{intt;cin>>t;t=round(t+0.5);// 计算 T_i + 0.5 的整数表示（等价于向上取整）intpos=find(t);// 二分查找第一个离开时间 >= t 的位置// cout << "t pos " << t << " " << pos << endl;cout<<maxH[pos]<<endl;// 输出从 pos 开始到末尾的所有高橋中的最大身高}return0;}

【运行结果】

4 31 4 26 5 3 5 15 9 4 3 4 5 6 31 26 15 15