P1008 67的快递驿站

一.解题思路

1.碎碎念

6767我有十几个快递取件码发你了下班记得帮我带回来😁 （看完如果对你有帮助点个赞呗）

2.题目分析

其实第一眼想到的思路依旧是暴力求解，把每天的存货标记出来再取最大值，但是很显然，测试集防的就是我，3个TLE，老实了

老老实实用差分数组做一下，题目最下面的提示已经说了该怎么做，那我就讲解一下原理吧

差分数组 本质上记录的是原数组相邻元素的差值

特点 将区间更新转化为两点更新

diff[i] = arr[i] - arr[i-1]

🌰：原数组是arr = [2 ,5 ,1 ,4]

那么差分数组就是：diff[0] = arr[0] = 2

​ diff[1] = arr[1]-arr[0] = 5-2=3

​ diff[2] = arr[2]-arr[1] = 1-5=-4

​ diff[3] = arr[3]-arr[2] = 4-1=3

​ diff = [2,3,-4,3]

因为差分数组只需要修改2个位置就可以完成区间的更新，所以他的效率十分之高，像在这道题目的前提下，传统方法需要频繁遍历整个区间，会大大增加时间复杂度，从而会导致TLE

所以，我们现在要做的事，就是在新快递到驿站的那一天，在库存清单上+1，下架的那一天-1。为什么这么做呢，我们已经知道差分是记录的是原数组相邻元素的差值，那么这道题里，给你一个时间[i,j]

新货上架的那一天i就相较于i-1天多了一个货，出库后那一天j+1就相较于j天少了一件货，这正是差分的一种应用形式

举个🌰

我们做的不是去统计当前有多少货，而是哪一天来了几个货，哪一天又出去了几个货，然后捏统计前缀和就好啦！（前缀和不会的去做P1004. flying的刷题记录，那一题我对前缀和做了比较完备的解释）

这里再解释一下为什么要用前缀和：

差分数组其实是区间更新，而前缀和是区间查询，二者之间类似于互逆运算，前缀和就是在还原出每一天货架上有多少快递

除此之外，类似统计人流量变化，温度变化等两点间变化的题目都可以考虑一下差分数组

理论存在，实践开始！

3.算法实现

对于区间 【L,R】 加 1，只需 diff[L]++，diff[R+1]--（我直接照搬的提示）

然后计算前缀和，找出最大值即可

4.复杂度

1.时间：O(n + m)

2.空间：O(n)

二.完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,m;
    cin>>n>>m;

    vector<pair<int,int>> num(m);
 
    for(int i=0;i<m;++i){
        cin>>num[i].first>>num[i].second;
    }

    vector<int> ans(n+2,0);
    for(int i = 0;i < m;++i){
        int l = num[i].first;
        int r = num[i].second;

        ans[l]++;
        ans[r+1]--;

    }
    vector<int> pre(n+2,0); 

    for(int i = 1;i <n+2;++i){
        pre[i]=pre[i-1]+ans[i];
    }

    cout << *max_element(pre.begin(),pre.end()) <<'\n';
    return 0;
}

PS：非专业题解！有任何错误记得联系我！！！