出题人题解 | #作物#

原题解链接：https://ac.nowcoder.com/discuss/149980

把每个植物成熟的时间投射到位置1上，将 $p [i]$ 减去 $\sum_{j=2}^{i} d[i]$ ，排序后形成了一个序列。

可以证明，每个药农只会采集一段区间。

题目转化成一个序列分成 $k$ 个区间求最小花费。

花费的计算可以用前缀和来表示， $S_{i}$ 表示成熟时间前缀和，那么转移方程。

f[[i]表示前i个采集完毕，出动了j个药农。

那么

$f[i][j]=\min (f[i][j-1]+(i-k) * p[i]-(s[i]-s[k]))$

推出斜率若转移到 $i$ 时 $k_{1}$ 比 $k_{2}$ 优那么

p[i]<\frac{\left(f\left[k_{1}\right][j-1]+s\left[k_{1}\right]\right)-\left(f\left[k_{2}\right][j-1]+s\left[k_{2}\right]\right)}{k_{1}-k_{2}}

可以 $O (n k)$ 做了

套上带权二分就 $A$ 了。

注意前缀和可能很多负数(虽然这不符合逻辑)，我们把绝对大小转换成相对大小，令 $p [1] = 0$ ,其余的都相对 $p [1]$ 做差，这样结果就都是正数。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define M 200010
#define LL long long
using namespace std;
LL dp[M], d[M], p[M], n, k, id[M], s[M], q[M], tm;
int note[M];
inline LL read() {
    char c = getchar(); LL x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
double X(int x) {
	return x;
}
double Y(int x) {
	return dp[x] + s[x];
}
double slope(int a, int b) {
	return (Y(a) - Y(b)) / (X(a) - X(b));
}
int DP(LL x) {
	int h = 1, t = 1;
	for(int i = 1; i <= n; i++) {
		while(h < t && (double)(p[i]) > slope(q[h],q[h + 1])) h++;
		dp[i] = dp[q[h]] + p[i] * (i - q[h]) - s[i] + s[q[h]] + x;
		note[i] = note[q[h]] + 1;
		while(h < t && slope(q[t],q[t - 1]) > slope(q[t], i)) t--;
		q[++t] = i;
	}
	return note[n];
}

int main() {
	n = read(), k = read();
	for(int i = 1; i <= n; i++) p[i] = read(), d[i] = i == 1 ? read() * 0 : d[i - 1] + read(), p[i] -= d[i]; 
	sort(p + 1, p + n + 1);
	for(int i = 2; i <= n; i++) p[i] = p[i] - p[1];p[1] = 0; 
	for(int i = 1; i <= n; i++) s[i] = s[i - 1] + p[i];
	LL L = 0, R = s[n] * (n - 1);
	while(L < R) {
		LL mid = (L + R) >> 1;
		if(DP(mid) <= k) R = mid - 1;
		else L = mid + 1;
	}
	DP(R + 1);
	cout << dp[n] - (R + 1) * k ;
	return 0;
}