摘要
Title: 1922. 懒惰的牛
Tag: 双指针、枚举、前缀和、差分
Memory Limit: 64 MB
Time Limit: 1000 ms

1922. 懒惰的牛

题意

这是一个炎热的夏日。
懒洋洋的奶牛贝茜想将自己放置在田野中的某个位置，以便可以在短距离内尽可能多地吃到美味的草。
贝茜所在的田野中共有 N 片草地，我们可以将田野视作一个一维数轴。
第 i 片草地中包含 gi 单位的青草，位置坐标为 xi。
不同草地的位置不同。
贝茜想选取田野中的某个点作为她的初始位置（可能是某片草地所在的点）。
只有一片草地与她的初始位置的距离不超过 K 时，贝茜才能吃到那片草地上的草。
如果贝茜选择最佳初始位置，请确定她可以吃到的青草最大数量。
思路
- 差分
  如果这个点有草的话，就将 $x-k$ 到 $x+k$ 都加上 $g$ ，最后前缀和统计最大值即可，复杂度为 $O(n)$
- 前缀和
  最优情况肯定是2K的草都吃上，所以就维护正好2K长的区间和即可，可以用前缀和进行维护，复杂度为 $O(n)$
- 双指针
  可以观察到两个指针都是单调的，那么就可以维护一个 $\le$ 2K的区间，复杂度为 $O(nlogn)$

代码

正常差分 2210ms

需要考虑边界情况

'''
Author: NEFU AB-IN
Date: 2022-01-19 19:13:13
FilePath: \ACM\Acwing\1922.py
LastEditTime: 2022-01-19 19:26:07
'''
N = int(1e6 + 10)
b = [0] * N
a = [0] * N

if __name__ == "__main__":
    n, k = map(int, input().split())
    for _ in range(n):
        g, x = map(int, input().split())
        a[max(0, x - k)] += g
        a[min(x + k + 1, int(1e6))] -= g
    res = 0
    for i in range(N):
        b[i] = b[max(0, i - 1)] + a[i]
        res = max(res, b[i])
    print(res)

map差分 2940ms

'''
Author: NEFU AB-IN
Date: 2022-01-19 19:36:30
FilePath: \ACM\Acwing\1922.1.py
LastEditTime: 2022-01-19 19:40:57
'''

from collections import Counter

d = Counter()

if __name__ == "__main__":
    n, k = map(int, input().split())
    for _ in range(n):
        g, x = map(int, input().split())
        d[x - k] += g
        d[x + k + 1] -= g
    res, sum = 0, 0
    for i in sorted(d.keys()):
        sum += d[i]
        res = max(res, sum)
    print(res)

前缀和 2320ms

'''
Author: NEFU AB-IN
Date: 2022-01-21 22:05:18
FilePath: \ACM\Acwing\1922.2.py
LastEditTime: 2022-01-21 22:24:50
'''

N = int(1e6 + 10)
lst = [0] * N

if __name__ == "__main__":
    n, k = map(int, input().split())
    maxn = 0
    for _ in range(n):
        g, x = map(int, input().split())
        # 因x能取到0，所以将x加一
        lst[x + 1] = g
    for i in range(1, N):
        lst[i] += lst[i - 1]
    res = 0
    for i in range(N):
        l = max(1, i - k)
        r = min(i + k, N - 1)
        res = max(res, lst[r] - lst[l - 1])
    print(res)

双指针 2814ms

'''
Author: NEFU AB-IN
Date: 2022-01-21 22:34:17
FilePath: \ACM\Acwing\1922.3.py
LastEditTime: 2022-01-21 23:31:56
'''
N = int(1e6 + 10)
lst = []

if __name__ == "__main__":
    n, k = map(int, input().split())
    maxn = 0
    for i in range(n):
        g, x = map(int, input().split())
        lst.append((x, g))
    lst.sort()
    j = 0
    res, sum = 0, 0
    for i in range(n):
        sum += lst[i][1]
        while j < i and lst[i][0] - lst[j][0] > 2 * k:
            sum -= lst[j][1]
            j += 1
        res = max(res, sum)
    print(res)

1922. 懒惰的牛

题意

思路

代码