[diary of supplementary questions] [2022 Niuke summer school 2] h-take the elevator

Pro

https://ac.nowcoder.com/acm/contest/33187/H

Sol

greedy , A better way to understand is weight .

Because rising and falling are inverse processes , So just talk about the idea of rising , The same goes for falling . On the rise , The first number entered x It must be less than the second number y, We can assume that people weigh 1, And the maximum weight of the elevator is m.

It's easy to think that it's best to consider the highest person first , So do it in descending order , So when we enumerate from top to bottom on the rise , The priority is y, And if you want to indicate that there is a person in the next interval , Should be in y It's about +1, Empathy , stay x This person has gone down , be -1.

After processing the weight change of each endpoint , Enumerate everyone from top to bottom , If the weight exceeds m, Have to open a new elevator to run , At the same time, record the highest floor of the newly opened elevator , Finally, get on and off the elevator max Is the number of elevator runs , The highest level of the rise and fall of the same number of trips （ Maintenance value ） take max, Again -1 ride 2 That's the answer. .

About sorting ： It must be higher and forward , What if the height is equal ？ Put first -1. It's easy to understand , Our practice is to turn the number of people into weight , So the smaller the weight, the more opportunities for others , And the weight is only -1 and 1, So when the height is equal , Put the light one in front .

Code

//By cls1277
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define endl '\n'

const LL maxn = 2e5+5;
LL n, m, k, w, c1, c2;
LL ans1[maxn], ans2[maxn];

struct Node {
    
    LL ops, weight;
};

vector<Node> a, b;

bool operator < (const Node &x, const Node &y) {
    
    if(x.ops!=y.ops) return x.ops>y.ops;
    return x.weight<y.weight;
}

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef DEBUG
    freopen("data.txt","r",stdin);
    #endif
    cin>>n>>m>>k;
    Fo(i,1,n) {
    
        LL x, y; cin>>x>>y;
        if(x<y) {
    
            a.push_back({
    x, -1});
            a.push_back({
    y, 1});
        } else {
    
            b.push_back({
    x, 1});
            b.push_back({
    y, -1});
        }
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for(auto it:a) {
    
        w += it.weight;
        if(w > m*c1) ans1[++c1] = it.ops;
    }
    w = 0;
    for(auto it:b) {
    
        w += it.weight;
        if(w > m*c2) ans2[++c2] = it.ops;
    }
    LL c = max(c1, c2), ans = 0;
    Fo(i,1,c) {
    
        ans += (max(ans1[i], ans2[i])-1)*2;
    }
    cout<<ans;
    return 0;
}