正经题解｜Arisu快递机器人

题面大意

给定$n$个时间段，每个时间段会占用编号$k + [l,r]$，求解过程中出现的最大编号总数.

思路解析

本质上就是求模拟最大容量的题目，可以设定u[i]表示当前$i$时所需编号数量。
对于每一个起始时间u[s]使得其初始数值赋为b，代表所需的编号容量，对于结束的时间段u[d]使其减b，该题则可变为最为简单的差分。

时间复杂度

时间复杂度$O(n)$

代码演示

#include<bits/stdc++.h>
using namespace std;
int n,s,e,b,u[10000005],answer,temp;
int main()
{
    cin >> n;
    while(n--)
    {
        cin >> s >> e >> b;
        u[s]=b; u[e]=-b; 
    }
    for(int i=1;i<=10000005;i++)
    {
        temp+=u[i]; //累加用的桶的数量
        answer = max(answer,temp);
    }
    cout << answer << endl;
    return 0;
}