“蔚来杯“2022牛客暑期多校训练营2 H.[Take the Elevator] 维护线段

H.Take the Elevator 模拟 题目分析

给定 k k k层楼的楼栋，现在有一个电梯从 1 1 1楼出发，最多承载 m m m人，电梯有故障，向下运行时必须到达 1 1 1楼方可改变方向。有 n n n个人希望从 a i a_i ai​楼层到达 b i b_i bi​楼层，问电梯至少需要跑多少趟。

设 a n s u p [ i ] ansup[i] ansup[i]表示向上走的第 i i i轮到达的最高的层数， a n s d o w n [ i ] ansdown[i] ansdown[i]表示向下走的第 i i i轮出发的最高层数，那么最终答案就是枚举轮数 i i i， a n s + = max ⁡ ( a n s u p [ i ] , a n s d o w n [ i ] ) ∗ 2 − 2 ans += \max(ansup[i], ansdown[i]) * 2 - 2 ans+=max(ansup[i],ansdown[i])∗2−2，得到最终答案。

那么可以分上下两个过程，分别存下所有的端点(带标记)，每个乘客分配的轮数可以通过 ⌈ m + c n t m ⌉ \lceil \frac{m + cnt}{m}\rceil ⌈mm+cnt​⌉得到。

Code

#include 
#pragma gcc optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

struct node{ int s, t; }up[N], down[N];

int ansup[N], ansdown[N];

inline void solve(){
    int n = 0, m = 0, k = 0; cin >> n >> m >> k;
    int upcnt = 0, downcnt = 0;
    for(int i = 1; i > a >> b;
        if(a