坐电梯时间限制1 秒空间限制32M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小 sun 非常懒所以他非常喜欢坐电梯但是他发现了一个问题当他在k kk楼想要坐电梯去1 11楼时如果比他高的楼层有人想坐电梯去1 11楼他就必须等待直到电梯把他楼上的人接完了才能到他的楼层来接他于是他是非常的苦恼。现在他想问问你如果他知道某个时刻所有想坐电梯的人所在的楼层他要等多久电梯才能到他的楼层。关于电梯电梯最开始在1 11楼每一秒可以上升或者下降一个楼层。在同一时刻有多个请求时电梯会优先处理最高楼层的请求。输入描述第一行两个整数n , k n, kn,k代表在当前时刻总共有n nn个去1 11楼的请求小 sun 在第k kk楼数据保证k kk不为1 11第二行共n nn个整数a i a_iai​每个整数代表一个请求所在的层数。输出描述输出一行他要等待的时间秒示例 1输入5 3 1 2 3 5 5输出6数据范围1 ≤ n ≤ 10 6 1 \le n \le 10^61≤n≤1062 ≤ k ≤ 10 8 2 \le k \le 10^82≤k≤1081 ≤ a i ≤ 10 8 1 \le a_i \le 10^81≤ai​≤108解题思路本题是贪心 分类讨论的简单模拟问题。电梯初始在 1 楼所有请求都是前往 1 楼且同一时刻有多个请求时电梯优先处理最高楼层的请求。小 sun 在k kk楼需要计算电梯到达k kk楼接他所需要等待的时间。1. 问题等价转化电梯的移动规则如下电梯从 1 楼出发先上升到当前所有请求中的最高楼层途中可以顺路接人但根据“优先处理最高楼层”的规则电梯会直接到达最高楼层再向下运行。所有请求的目标都是 1 楼因此电梯在接到最高楼层的人后会开始下降并在下降过程中依次接走沿途楼层的人。小 sun 在k kk楼电梯接到他的前提是电梯在下降过程中经过k kk楼或者k kk楼本身就是最高请求楼层。设所有请求中的最高楼层为m x mxmx不包括小 sun 所在的k kk楼但若k kk更高则k kk本身也是请求。2. 分类讨论情况一m x ≤ k mx \le kmx≤k说明没有比小 sun 更高的请求或者最高请求就是小 sun 自己所在的楼层。此时电梯会直接上升到k kk楼因为k kk是最高请求所需时间为从 1 楼到k kk楼的上升时间ans k − 1 \text{ans} k - 1ansk−1情况二m x k mx kmxk说明存在比小 sun 更高的请求。电梯会先上升到最高楼层m x mxmx耗时m x − 1 mx - 1mx−1秒然后从m x mxmx下降到k kk楼耗时m x − k mx - kmx−k秒。因此总等待时间为ans ( m x − 1 ) ( m x − k ) 2 m x − k − 1 \text{ans} (mx - 1) (mx - k) 2mx - k - 1ans(mx−1)(mx−k)2mx−k−13. 算法实现读入n , k n, kn,k。遍历所有请求楼层a i a_iai​求出最大值m x mxmx。根据上述分类计算答案若m x ≤ k mx \le kmx≤k输出k − 1 k - 1k−1否则输出2 m x − k − 1 2mx - k - 12mx−k−1。4. 复杂度分析时间复杂度只需一次遍历求最大值O ( n ) O(n)O(n)。n ≤ 10 6 n \le 10^6n≤106完全可行。空间复杂度仅使用常数个变量O ( 1 ) O(1)O(1)。总结通过分析电梯“优先处理最高楼层”的规则将等待时间分为两种情况最高请求不高于k kk时电梯直接到达k kk楼最高请求高于k kk时电梯先上升至最高楼层再下降至k kk楼。分类计算即可得到答案方法简单高效。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,k;cinnk;ll mx0,v;for(ll i0;in;i){cinv;if(vmx)mxv;}if(mxk)mxk-1;elsemxmx-1mx-k;coutmx\n;return0;}