H. Take the elevator greedy

H
greedy

The question

The meaning of the title in the posted Title Solution , There is actually a mistake here , High floor $k$, The passenger capacity is limited to $m$ .

Ideas

Because the direction cannot be changed during the descent , And those who go up must take the elevator when they go up , People who go down must take the elevator when they go down （ crap ）, Therefore, we might as well divide people into two directions: upward and downward . It can be found that the two are similar , Let's first consider the ascending people .

Consider the simple case first ： Take at most on each ascent $m$ people . And the running time of the elevator is obviously Only with the one who reaches the highest floor About that person , therefore , In this case, we greedily choose to reach the height every time $m$ It is the optimal solution for tall people to take the elevator .

On this basis , You need to take as many people as possible on each ascent . So long as Press the height of the finish line from top to bottom, and select it as often as possible $m$ personal that will do .

To be specific , We can record the starting position of each ascending person $st$ And end position $ed$, Use prefix and maintain how many people are in the current elevator , If exceeded $m$ People need to take the next elevator , In this process, record the total number of upward elevators and the highest floor they need to reach . The same goes for the downlink , See code for details .

Code

int n, m, k;
struct Node {
    
    int pos, d;    //pos Indicate location ,d=1 It means getting on the elevator  d=-1 Means getting off the elevator 
    bool operator < (const Node &x) const {
    
        if(pos != x.pos) return pos > x.pos;
        return d < x.d;
    }
};
vector<Node> up, down;
void solve() {
    
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) {
    
        int st, ed;
        cin >> st >> ed;
        if(st < ed) {
    
            up.pb({
    st, -1});
            up.pb({
    ed, 1});
        }
        else {
    
            down.pb({
    st, 1});
            down.pb({
    ed, -1});
        }
    }
    sort(up.begin(), up.end());
    sort(down.begin(), down.end());
    int cnt = 0;
    vector<int> up_max, down_max;    // Means every rise / The maximum height reached by descent ,size() Number of times 
    for(auto x : up) {
    
        cnt += x.d;    // Maintain the current number of people in the elevator , If it exceeds, you need to wait for the next elevator 
        if(cnt > up_max.size() * m) up_max.pb(x.pos);
    }
    for(auto x : down) {
    
        cnt += x.d;
        if(cnt > down_max.size() * m) down_max.pb(x.pos);
    }
    int mx = max(up_max.size(), down_max.size());// Total round trips , Is the maximum value in one-way .
    int ans = 0;
    for(int i = 0; i < mx; i++) {
    
        cnt = 0;
        if(up_max.size() > i) {
    
            chmax(cnt, up_max[i]);
        }
        if(down_max.size() > i) {
    
            chmax(cnt, down_max[i]);
        }
        ans = ans + (cnt-1) * 2;
    }
    cout << ans << endl;
}