作物

[编程题]作物

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

山坡上有一个经济作物组成的序列

序列长度为n，第i个植物成熟时间为p_i,第i个植物与第i - 1 个植物距离为d_i

一共有k个药农，每个药农将以1的速度从位置1出发, 你可以自由安排每个药农的出发时间，当一个药农走到某个位置时，若该植物己经成熟，那么将其收获

植物成熟后若未被收获每秒损失1的价值，求最小损失价值

第一个植物的坐标为1

输入描述:

第一行两个整数n, k
第二行到第n+1行每行两个整数p_i, d_i
_{特别的，你可以认为d₁没有意义}

输出描述:

一个非负整数表示最小代价

示例1

输入

输出

说明

样例解释：四个药农的出发时间分别为(1, -8, -19, -34)

备注:

对于100%的数据：n ≤ 2 * 10⁵， k ≤ 2000， p_i ≤ 10⁹， d_i ≤ 10⁴
根据相对论，药农的出发时间可以为负！
必须采摘所有植物，损失不可能为负数

题目并不难

算法知识视频讲解

耕云种月

发表于 2022-01-30 19:46:52

原题解链接：https://ac.nowcoder.com/discuss/149980 把每个植物成熟的时间投射到位置1上，将 p[i]p[i]p[i] 减去 ∑j=2id[i]\sum_{j=2}^{i} d[i]∑j=2id[i] ，排序后形成了一个序列。可以证明，每个药农只会采集一段区展开全文