摘要
Title: 1952. 金发姑娘和 N 头牛
Tag: 差分，map，离散化
Memory Limit: 64 MB
Time Limit: 1000 ms

1952. 金发姑娘和 N 头牛

题意

你可能听过关于金发姑娘和三只熊的经典故事。
然而，鲜为人知的是，金发姑娘最终成了一个农民。
在她的农场中，她的牛棚里有 N 头奶牛。
不幸的是，她的奶牛对温度相当敏感。
对于奶牛 i，使其感到舒适的温度为 Ai…Bi。
如果金发姑娘将牛棚的恒温器的温度 T 设置为 T<Ai，奶牛就会觉得冷，并会产出 X 单位的牛奶。
如果她将恒温器的温度 T 设置在 Ai≤T≤Bi，奶牛就会感到舒适，并会产出 Y 单位的牛奶
如果她将恒温器的温度 T 设置为 T>Bi，奶牛就会觉得热，并会产出 Z 单位的牛奶。
正如所期望的那样，Y 的值始终大于 X 和 Z。
给定 X,Y,Z 以及每头奶牛感到舒适的温度范围，请计算通过合理设定恒温器温度，金发姑娘可获得的最大产奶量。
恒温器温度可设置为任何整数。
思路

还是一个经典差分题
可以看到N最多20000，而A,B最大1e9，说明需要离散化
- 手写离散化，常数小，代码量大
- map离散化，常数大，代码量小（每次操作map为log）
总体思路就是，将每个牛的温度范围化为三个区间：
- [-INF, L - 1]
- [L, R]
- [R + 1, INF]
每个区间均加上该区间对应的牛奶量，依次加上所有牛的，一定会存在一个最大值，这个就是答案
区间覆盖我们就用离散化的差分进行优化
找最大值时，用前缀和恢复原数组即可O(n)找出

代码

map离散化 1581ms

'''
Author: NEFU AB-IN
Date: 2022-01-15 11:19:39
FilePath: \ACM\Acwing\1952.py
LastEditTime: 2022-01-15 14:33:57
'''
'''
可能有多个区间满足最大覆盖
可能区间中含有多个值
'''
from collections import Counter

INF = float('inf')
d = Counter()


def solve():
    n, x, y, z = map(int, input().split())
    for _ in range(n):
        a, b = map(int, input().split())
        d[-INF] += x
        d[a] += (y - x)
        d[b + 1] -= (y - z)
        d[INF] -= z
    res = 0
    sum = 0
    for i in sorted(d.keys()):
        sum += d[i]
        res = max(res, sum)
    print(res)


if __name__ == "__main__":
    solve()

手写离散化 1265ms

首先xs为离散化数组，b为差分数组（要开两倍，因为最多2N个点）
离散化的思想就是将数值进行排序并去重后映射成对应的下标
查询某数的下标时可以采用二分，找大于等于x的第一个数的下标（其实就是lower_bound）
- 手写二分
- 或者用自带的库

'''
Author: NEFU AB-IN
Date: 2022-01-15 15:05:19
FilePath: \ACM\Acwing\1952.1.py
LastEditTime: 2022-01-16 00:25:22
'''

import bisect
# 全局变量尽量只是定义

INF = int(2 * 1e9)
N = 20020
xs = [-INF, INF]
lst = []
b = [0] * (2 * N)


def find(x):
    l = 0
    r = len(xs) - 1
    while l < r:
        mid = l + r >> 1
        if xs[mid] >= x:
            r = mid
        else:
            l = mid + 1
    return r


# def find(x):
#     return bisect.bisect_left(xs, x)

if __name__ == '__main__':
    # xs.append(-INF)
    # xs.append(INF)
    n, x, y, z = map(int, input().split())
    for _ in range(n):
        l, r = map(int, input().split())
        lst.append((l, r))  #存原数组
        xs.append(l)  #存需离散的值
        xs.append(r + 1)

    xs = list(set(xs))  #去重并排序，这样每个 l 和 r + 1 都有一个唯一的下标对应，即数值对应下标了
    # 故xs可以说是存的对应关系
    xs.sort()
    for i in range(n):
        L = find(lst[i][0])  #找出 l 在xs中对应的下标
        R = find(lst[i][1] + 1)  #找出 r + 1 在xs中对应的下标
        # b为差分数组，此时相当于map
        b[0] += x
        b[L] += (y - x)
        b[R] -= (y - z)
        b[len(xs) - 1] -= z

    sum = 0
    res = 0
    # 从下标0开始枚举，枚举b中的值，范围就是xs的范围
    for i in range(len(xs)):
        sum += b[i]
        res = max(res, sum)
    print(res)

1952. 金发姑娘和 N 头牛

题意

思路

代码