2022 Nioke Multi-School Training Session H Question H Take the Elevator

题目链接

H题 Take the Elevator

题目大意

大概意思就是,Gave us a broken elevator,And some information about the passengers who need to take the elevator and the maximum capacity of the elevatorm.Ask us the minimum time required for the elevator to transport all passengers to the command floor.

题解

很明显的贪心题,但是不太好想,Here is an idea.
We consider ascending passengers and descending passengers separately,Because if the elevator starts to descend,Then it cannot go up any further;So we let the elevator go as high as possible every time you lie down,Then the time it takes for each trip is to take the largest one for ascending and descending;
主要实现方法：
Suppose the current moving range is $[l,r]$,假设$l<r$,Then the current is the upward direction,我们在$l$处-1,在$r$处+1,That is, into the elevator-1,出电梯+1; Then consider the highest point,The current highest point is the highest position the elevator will reach;
In the same way, consider the direction of descent：假设当前区间为$[l,r]$, $l>r$,$l$处-1, $r$处+1.Then sort all the points,Consider the highest position first,大概思路就是这样,细节看代码吧.

#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;  // Rising and falling passengers are stored separately
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;  // The maximum heights for ascent and descent are stored separately for each trip
	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;
}