自动搬运

查看原文

来自洛谷，原作者为

	Error_Eric 终究还是意难平

搬运于2025-08-24 22:38:39，当前版本为作者最后更新于2024-10-26 16:41:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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))