坐电梯【牛客tracker 每日一题】

坐电梯

时间限制：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≤106
• 2 ≤ k ≤ 10 8 2 \le k \le 10^82≤k≤108
• 1 ≤ 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 - 1ans=k−1

• 情况二：m x > k mx > kmx>k
  说明存在比小 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−1

3. 算法实现

1. 读入n , k n, kn,k。
2. 遍历所有请求楼层a i a_iai​，求出最大值m x mxmx。
3. 根据上述分类计算答案：
   • 若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楼。分类计算即可得到答案，方法简单高效。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,k;cin>>n>>k;ll mx=0,v;for(ll i=0;i<n;i++){cin>>v;if(v>mx)mx=v;}if(mx<=k)mx=k-1;elsemx=mx-1+mx-k;cout<<mx<<'\n';return0;}