专栏文章

题解：P7747 [COCI 2011/2012 #3] TRAKA

jj23wuyifan
P7747题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minvmh7z
此快照首次捕获于
2025/12/02 09:05
3 个月前
此快照最后确认于
2025/12/02 09:05
3 个月前
查看原文

Solution

设 f[i]f[i] 表示第 ii 辆汽车开始加工的时间，t[i]t[i] 表示对每个工人完成工作时间做的前缀和，g[i]g[i] 表示题目中的 f[i]f[i]。
题目中的：根据公司政策，一个工人完成他的工作后，他必须立即将工作交给下一个工人，不得拖延。表明每个工人 jj 开始加工第 ii 的时间一定大于等于他加工完第 ii 辆车的时间。就有：
f[i]+t[j−1]×g[i]≥f[i−1]+t[j]×g[i−1]f[i] + t[j-1] \times g[i] \ge f[i - 1] + t[j] \times g[i - 1]
f[i]≥f[i−1]+t[j]×g[i−1]−t[j−1]×g[i]f[i] \ge f[i - 1] + t[j] \times g[i - 1] - t[j-1] \times g[i]
f[i]=f[i−1]+max⁡j=1n(t[j]×g[i−1]−t[j−1]×g[i])f[i] = f[i - 1] + \max_{j=1}^{n} (t[j] \times g[i - 1] - t[j-1] \times g[i])
暴力枚举 jj，可以获得 4040 分。
考虑斜率优化，式子右边提取出 g[i−1]g[i-1] 或 g[i]g[i]，得到：
f[i]=f[i−1]+g[i−1]×max⁡j=1n(t[j]−t[j−1]×g[i]g[i−1])f[i] = f[i - 1] + g[i-1] \times \max_{j=1}^{n} (t[j] - t[j-1] \times \frac{g[i]}{g[i-1]})
t[j]t[j] 相当于是 yy，t[j−1]t[j-1] 是 xx，g[i]g[i−1]\frac{g[i]}{g[i-1]} 是 kk。接下来就是斜率优化的套路了。因为 kk 不具有单调性，所以需要二分，时间复杂度就是 O(nlog⁡n)O(n \log n)。

Code

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int f[N], t[N], g[N], n, m, q[N];
//f[i] 表示第 i 辆车的最早开始时间
inline int X(int i) {return t[i - 1];}
inline int Y(int i) {return t[i];}
signed main() {
	cin >> n >> m;
	int r = 0;
	for (int i = 1; i <= n; i ++) {
		cin >> t[i], t[i] += t[i - 1];
		//维护上凸壳(斜率递减)，x = t[i - 1],y = t[i]
		while (r > 1 && (Y(i) - Y(q[r])) * (X(q[r]) - X(q[r - 1])) > (Y(q[r]) - Y(q[r - 1])) * (X(i) - X(q[r])))r --;
		q[++ r] = i;
	}
	for (int i = 1; i <= m; i ++) cin >> g[i];
	f[1] = 0;
	for (int i = 2; i <= m; i ++) {
		//k = g[i] / g[i - 1]
		int ll = 1, rr = r, res;
		//二分找最值
		while (ll <= rr) {
			int mid = ll + rr >> 1;
			//斜率 <= k
			if ((Y(q[mid + 1]) - Y(q[mid])) * g[i - 1] <= (X(q[mid + 1]) - X(q[mid])) * g[i]) {
				res = mid;
				rr = mid - 1;
			} else ll = mid + 1;
		}
		f[i] = f[i - 1] + g[i - 1] * t[q[res]] - t[q[res] - 1] * g[i];
	}
	cout << f[m] + t[n] * g[m];
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...