社区讨论
求助
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 条回复,欢迎继续交流。
正在加载回复...