差分
思路:一开始看起来我以为是个二分,但是再写 $check$ 函数的时候,发现无从下手,因为无法判断是在哪一段,所以抛弃了原来思路;然后观察到 $n$ 的数据范围很小,但是 $a_i$ 的值域很大。
我们不妨先来考虑一个针对于此问题的弱条件下要怎么写:即假如 $a_i$ 的值域很小的时候。
不难想到我们有两个比较好想的解法。
为了方便,我们把 某个温度对应的产奶量 表示为 代价 。
-
直接枚举所有的 $T$ ,然后遍历数组,求出当前的最大代价,时间复杂度是 $O(nN)$ 的,其中 $n$ 代表数组的大小,$N$ 代表值域;
-
因为存在这样的特点:假如
x y z
分别是2 3 1
,那么只考虑一头牛的情况下,最后所有的代价一定是2 2 2 2 ... 2 2 2 3 3 3 3 ... 3 3 3 3 1 1 1 ... 1 1 1 1
;那么很多头牛的时候呢?那就是若干个区间的叠加和。一看到某个区间的和其实我们就不难想到用差分了,想到差分这道题就解出来一大半了。时间复杂度为 $O(n + N)$ 的,空间复杂度为 $O(N)$,其中 $n$ 代表数组的大小,$N$ 代表值域;
回到原问题,现在的 $a_i$ 因为值域非常的大,我们不可能开一个大小为$10^9$的数组来模拟差分,所以我们要离散化,或者直接偷懒用一个 $map$ 维护即可,因为 $map$ 本身就自带有序。
然后再差分的时候,我们有:
$$mp[0] ~+= ~x \\ \\ mp[a - 1 + 1] ~-= ~x$$
$$mp[a] ~+= ~y \\ \\ mp[b + 1] ~-=~ y$$
$$mp[b + 1] ~+= ~z \\ \\ mp[10^9] ~-= ~z$$
分别代表在 $[0, a - 1], [a, b], [b + 1, \infty]$ 进行区间加法,也就是差分运算。
最后遍历一遍 $map$ ,边求前缀和边记录答案。
时间复杂度:$O(n \log N)$ ,其中 $n$ 代表数组的大小,$N$ 代表值域
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
int n, x, y, z;
map<int, int> mp;
int main() {
cin >> n >> x >> y >> z;
for(int i = 0; i < n; i ++) {
int a, b;
cin >> a >> b;
mp[0] += x; mp[a] -= x;
mp[a] += y; mp[b + 1] -= y;
mp[b + 1] += z; mp[1e9] -= z;
}
ll ans = 0, now = 0;
for(auto [k, v] : mp) {
now += v;
ans = max(ans, now);
}
return cout << ans, 0;
}
应该不是单峰函数吧,例如x=0,y=5,z=0,然后有两头牛,温度范围区间不相交,那么就会有两个峰值
有道理,欠考虑了,感谢指正!
喵喵子tql
%%lqmm
我就写的二分(ac了 不知道是不是数据太弱了还是二分就可以做🤣
哈哈哈厉害!我回去研究一下你的代码!