题解：P8387 [COI2021] Autobahn

· · 题解

Statement

Link

题目的意思有点迷，附上样例 1 的图形化解释。

Sol

注意到 1\le X,l_i,t_i,r_i\le 10^9。这个数据表示我们不能算出每个时刻的车子的数量。但是车子数量和状态的「改变次数」是 O(n) 的，所以我们可以很简单且套路地把车子数量和状态改变的时间点排序，并且算出每个「时间区间」内，需要补交车费的车子数量。换言之，如果 f(x) 表示第 x 小时需要补交车费的车子数量，则 f(x) 的图像是由 O(n) 个水平线段组成的。（严格来说，\sout{f(x)} 是离散的，但是我找不到更好的文字表述了）

有一个在此类套路中常见的结论，就是最佳选择一定可以让其中一段落在线段的断点上。证明也很简单：

不妨假设一段区间 [l,r] 是最优的，且两端都不在断点。那么往左滑动一格价值（减免费用）的减小量（必然非负）肯定等于往右滑动一格价值（减免费用）的增加量（必然非正）。则价格变化为 0, 这个区间可以一直滑动直到碰到断点即可。

只需要用 尺取法 算出每一段可能选择的价值即可。每段线段只会被加入/删除一次，所以复杂度是 O(n) 的，算上排序就是 O(n\log n)。卷怪可以用基数排序优化到 O(n) 但是没有必要。

Code

有点丑陋。

n, k, x = map(int, input().split())
events = []
for i in range(n):
    li, ti, ri = map(int, input().split())
    events.append((li, 1))
    events.append((ri + 1, 2))
    if li + ti < ri+1:
        events.append((li + ti, 4))
        events.append((ri + 1, 3))

events.sort(key = lambda x: x[0] * 5 + x[1])
totalcount, expirecount, ranges = 0, 0, []
for ei in events:
    if ei[1] == 1: totalcount += 1
    elif ei[1] == 2: totalcount -= 1
    elif ei[1] == 3: expirecount -= 1
    elif ei[1] == 4: expirecount += 1
    add = (ei[0], expirecount if totalcount >= k else 0)
    if len(ranges)>0 and ranges[-1][1] == add[1]:
        pass
    elif len(ranges)>0 and ranges[-1][0] == ei[0]:
        ranges[-1] = add
    else: ranges.append(add)
events = None

def value(pos : int, r: list) -> int:
    if pos == len(r) -1: return 0
    else : return r[pos][1] * (r[pos+1][0] - r[pos][0])
def fun(e : list):
    laste, payment, ans = 0, 0, 0
    for i, ei in enumerate(e[:-1]):
        while laste+1 < len(e) and e[laste+1][0] <= ei[0] + x:
            payment += value(laste, e)
            laste += 1
        ans = max(ans, payment + e[laste][1] * (ei[0] + x - e[laste][0]))
        payment -= value(i, e)
    return ans
a1 = fun(ranges)
ranges2 = [(0,0)] + [(ranges[-1][0] - ranges[i][0] +1, ranges[i-1][1]) for i in range(len(ranges)-1, 0, -1)] # 只枚举了左端点，所以反过来再做一遍
a2 = fun(ranges2)
print(max(a1, a2))