社区讨论

求助

P2365任务安排参与者 3已保存回复 16

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
16 条
当前快照
1 份
快照标识符
@lo5dpxsf
此快照首次捕获于
2023/10/25 14:33
2 年前
此快照最后确认于
2023/11/02 11:28
2 年前
查看原帖
CPP
for(int i=1;i<=n;i++){
	while(l<r&&(t[i]+s)*(c[q[l]]-c[q[l+1]])<=f[q[l]]-f[q[l+1]]) l++;
	f[i]=f[q[l]]+t[i]*(c[i]-c[q[l]])+s*(c[n]-c[q[l]]);
	while(l<r&&(c[i]-c[q[r]])*(f[q[r]]-f[q[r-1]])>=(c[q[r]]-c[q[r-1]])*(f[i]-f[q[r]])) r--;
  //这里这个while循环为什么是这样子?
  //这里是交叉相乘,f的那一项是Y,因此左边代表r-1与r的斜率,右边代表i与r的斜率。
  //那么,此题维护的是单调递增的斜率,那么应该保证尾部斜率大于当前斜率(i点与q[tt]点斜率),也就是尾部斜率小于等于当前斜率时弹出队尾
  //但是代码中是 尾部斜率(左)大于当前斜率(右) 啊
	q[++r]=i; 
} 

回复

16 条回复,欢迎继续交流。

正在加载回复...