金发姑娘和N头牛

原题链接

https://www.acwing.com/problem/content/1954/

题目分析

根据题目，把每头奶牛在不同温度下的产奶量列出来，可以构成一个n*T的矩阵，其中n表示奶牛数量，T表示最大温度。
就像下面的矩阵一样。

XXXYYYZZZZ

XXYYYZZZZZ

XYYYYZZZZZ

我们的目标就是要找到和最大的一列的和。

差分算法

因为T比较大，所以直接暴力枚举T肯定是不可行的。观察矩阵可以发现，每一行的值都是三个区间，区间[0,$A_i$-1],[$A_i$,$B_i$],[$B_i$+1,+无穷]，显然可以用差分来表示。

然而传统差分数组不能够表示这么大的温度，所以需要用map来表示差分的值。

时间复杂度

在插入map数组的时候，每次操作消耗$logn$的时间，操作的6n次。
在遍历map数组的时候，由于其有序的性质，只需要n的时间。

最终时间复杂度为$O(nlogn)$

C++ 代码

#include<cstdio>
#include<map>
using namespace std;
map<int,int> mp;
int main(){
    int n,x,y,z;
    scanf("%d%d%d%d",&n,&x,&y,&z);
    int l,r;
    for(int i=0;i<n;i++){
        scanf("%d%d",&l,&r);
        mp[0]+=x;
        mp[l]=mp[l]-x+y;
        mp[r+1]=mp[r+1]-y+z;
    }
    int mx=0,cur=0;
    for(auto iter:mp){
        cur+=iter.second;
        if(cur>mx){
            mx=cur;
        }
    }
    printf("%d\n",mx);
    return 0;
}