2022牛客多校训练第二场 H题 Take the Elevator

题目链接

H题 Take the Elevator

题目大意

大概意思就是，给了我们一部损坏的电梯，以及一些需要乘坐电梯的乘客的信息以及电梯的最大容量m。问我们电梯把所有乘客都运送到指令楼层所需要的最小时间。

题解

很明显的贪心题，但是不太好想，在这里给一个思路。
我们分别考虑上升的乘客和下降的乘客，因为电梯如果开始下降了，那么它就不能再上升了；所以我们让电梯每一躺尽可能走的高，那么每一趟所花费的时间就是上升的下降取一个最大的；
主要实现方法：
假设当前移动区间为 $[l,r]$，假设$l<r$，那么当前即为上升方向，我们在$l$处-1，在$r$处+1，也就是进电梯-1，出电梯+1; 然后考虑最高的点，当前最高的点即是电梯要到达的最高位置；
同理再考虑下降方向：假设当前区间为$[l,r]$, $l>r$，$l$处-1， $r$处+1.然后对所有点进行排序，先考虑最高的位置，大概思路就是这样，细节看代码吧。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
typedef struct node
{
    
	int pos, type;
	bool operator < (const struct node &w) const {
    
		if(pos != w.pos) return pos > w.pos;
		return type < w.type;
	}
}Node;
vector<Node> up, down;  // 分别存储上升和下降的乘客
int n, m, k;
signed main()
{
    
	cin >> n >> m >> k;
	for(int i = 0; i < n; i ++){
    
		int a, b; cin >> a >> b;
		if(a < b) {
    
			up.push_back({
    a, -1});
			up.push_back({
    b, 1});
		}else{
    
			down.push_back({
    a, 1});
			down.push_back({
    b, -1});
		}
	}
	vector<int> t1, t2;  // 分别存储每一趟上升和下降的最大高度
	sort(up.begin(), up.end());
	sort(down.begin(), down.end());
	int temp = 0;
	for(auto item : up) {
    
		temp += item.type;
		if(temp > t1.size() * m) t1.push_back(item.pos);
	}
	temp = 0;
	for(auto item : down) {
    
		temp += item.type;
		if(temp > t2.size() * m) t2.push_back(item.pos);
	}
	int res = 0;
	for(int i = 0; i < t1.size() || i < t2.size(); i ++){
    
		temp = 0;
		if(i < t1.size()) temp = max(temp, t1[i]);
		if(i < t2.size()) temp = max(temp, t2[i]);
		res += (temp - 1) * 2;
	}
	cout << res << endl;
}