"NIO Cup" 2022 Nioke Summer Multi-School Training Camp 2 H.Take the Elevator

题意：
The capacity of an elevator is m , And when descending, you can only turn when you reach the first floor.有 n Individuals need to ride,The starting and ending points of each person are respectively li , ri .Ask from the first floor,meet all passenger needs,The shortest time to finally get back to the first floor.

思路：
Connect the passenger's origin and destination,Convert start and end points to left and right endpoints,abstract into points,It becomes a problem similar to interval coverage.

It's just that the upstairs and downstairs are dealt with separately here,However, the two cases are basically the same.Because you can't turn midway when descending,We definitely want each ascent to be as low as possible,And the current passenger on the highest floor will be picked up sooner or later（送达）的.

Therefore, a greedy algorithm is used,In both cases, the right endpoint is sorted from largest to smallest,维护一个优先队列.对于每个点,Points in the priority queue that are larger than the current right endpoint are placed firstpop掉,Then add it if it's not full,Otherwise wait for the next round,Place the rightmost endpoint of each round -1 存下.

Finally, after sorting the two cases,Keep taking the maximum value*2,Add up to get the answer

Code:

#include <bits/stdc++.h>
// #define debug freopen("_in.txt", "r", stdin);
#define debug freopen("_in.txt", "r", stdin), freopen("_out.txt", "w", stdout);
typedef long long ll;
typedef unsigned long long ull;
typedef struct Node *bintree;
using namespace std;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll maxn = 1e6 + 10;
const ll maxm = 2e6 + 10;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-8;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

ll T, n, m, q, d, kase = 0;
ll arr[maxn];

struct Node
{
    
    ll l, r;
    bool operator<(Node other) const
    {
    
        if (r != other.r)
            return r > other.r;
        else
            return l > other.l;
    }
} nodes[4][maxn];

priority_queue<ll> que1, que2;

vector<ll> vec1, vec2;

void solve()
{
    
    scanf("%lld%lld%lld", &n, &m,&q);
    ll cnt1 = 0, cnt2 = 0;
    for (ll i = 1; i <= n; i++)
    {
    
        ll l, r;
        scanf("%lld%lld", &l, &r);
        if (l > r)
        {
    
            nodes[1][++cnt1] = {
    r, l};
        }
        else
        {
    
            nodes[2][++cnt2] = {
    l, r};
        }
    }
    sort(nodes[1] + 1, nodes[1] + 1 + cnt1);
    sort(nodes[2] + 1, nodes[2] + 1 + cnt2);
    ll wc = 0, zo = cnt2, now = 2;
    while (zo > 0)
    {
    
        while(!que1.empty()) que1.pop();
        ll num=zo;
        vec2.push_back(nodes[now][1].r - 1);
        que1.push(nodes[now][1].l);
        num--;
        for (ll i = 2; i <=zo; i++)
        {
    
            while (!que1.empty() && que1.top() >= nodes[now][i].r)
            {
    
                // printf("%lld %lld\n",que1.top(),nodes[now][i].r);
                que1.pop();
            }
            if (que1.size() < m)
            {
    
                que1.push(nodes[now][i].l);
                num--;
            }
            else
            {
    
                // printf("%lld %lld\n",nodes[now][i].l,nodes[now][i].r);
                nodes[2-now][++wc]=nodes[now][i];
            }
        }
        now=2-now;
        wc=0;
        zo=num;
    }
    // printf("1\n");
    wc = 0, zo = cnt1, now = 1;
    while(!que1.empty()) que1.pop();
    while (zo > 0)
    {
    
        while(!que1.empty()) que1.pop();
        ll num=zo;
        vec1.push_back(nodes[now][1].r - 1);
        que1.push(nodes[now][1].l);
        num--;
        for (ll i = 2; i <=zo; i++)
        {
    
            while (!que1.empty() && que1.top() >= nodes[now][i].r)
            {
    
                que1.pop();
            }
            if (que1.size() < m)
            {
    
                que1.push(nodes[now][i].l);
                num--;
            }
            else
            {
    
                nodes[1-now][++wc]=nodes[now][i];
            }
        }
        now=1-now;
        wc=0;
        zo=num;
    }
    ll sz1=vec1.size();
    ll sz2=vec2.size();
    // printf("%lld %lld\n",sz1,sz2);
    sort(vec1.begin(),vec1.end());
    sort(vec2.begin(),vec2.end());
    ll ans=0;
    while(sz1>0&&sz2>0)
    {
    
        ans+=max(vec1[sz1-1],vec2[sz2-1])*2;
        sz1--;
        sz2--;
    }
    // printf("%lld\n",ans);
    while(sz1>0)
    {
    
        ans+=vec1[sz1-1]*2;
        sz1--;
    }
    while(sz2>0)
    {
    
        ans+=vec2[sz2-1]*2;
        sz2--;
    }
    printf("%lld\n",ans);
}

signed main()
{
    
    // debug;
    // scanf("%lld", &T);
    T=1;
    while (T--)
    {
    
        solve();
    }
}