思路
我们可以吧每个奶牛的产奶化成3个温度区间
【0,(l-1)】,【l,r】,【(r+1),1e9】
吐槽一句:
奶牛呆的温度一般是夏季不超过30度,春冬是8-20度(来源于百度百科)
这超过100度就可以吃肉了~~~
观察题目数据范围,温度是0-1e9的范围,
对于每个区间,产奶量分别为:x,y,z
如果抛开温度范围限制,就是一道差分
对于每只奶牛的三个温度区间分别加上x,y,z,最后只需要找一夏哪一个温度点上,数值最大即可
对于区间范围很大,区间中点的个数较少的情形,我们采用离散化(或用map来存储)
具体实现
由于奶牛数量N最大为2e5,则最多出现的温度区间端点为,2N,因此我们需要开40000大小的alls数组来存放端点。
同时为了记录每个端点的差分数组的值,这里再开一个cnt数组(也可以使用pair,x存端点,y存值)
由于构造的是差分数组,会用到“i-1”为了方便起见,我们的下标从1开始
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
int n,x,y,z,k = 1;//k记录当前可用的下一端点下表,去重后表示共有的端点个数
int alls[40010],cnt[40010];//alls为端点,cnt为差分数组
vector<PII> tp;//用来存每个奶牛的最适温度区间
int find(int x)//二分寻找映射前的alls下标
{
int l = 1,r = k;
while(l<r){
int mid = l+r>>1;
if(alls[mid]>=x) r = mid;
else l = mid+1;
}
return l;
}
void insert(int l,int r,int c)//差分插入操作
{
cnt[l]+=c;
cnt[r+1]-=c;
}
int main()
{
cin>>n>>x>>y>>z;
for(int i = 0;i<n;i++){
int l,r;
cin>>l>>r;
tp.push_back({l,r});
alls[k++] = l;
alls[k++] = r;
}
k--;
sort(alls+1,alls+k+1);
k = unique(alls+1,alls+k+1)-alls;//去重操作
for(auto i:tp)
{
int l = find(i.x);
int r = find(i.y);
insert(1,l-1,x);
insert(l,r,y);
insert(r+1,k,z);
}
int res = -1e9;
for(int i = 1;i<=k;i++){
cnt[i]+=cnt[i-1];
res = max(res,cnt[i]);
}
cout<<res;
return 0;
}