求助
  • 板块P2365 任务安排
  • 楼主Kniqht
  • 当前回复16
  • 已保存回复16
  • 发布时间2023/10/25 14:33
  • 上次更新2023/11/2 11:28:38
查看原帖
求助
315205
Kniqht楼主2023/10/25 14:33
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; 
} 
2023/10/25 14:33
加载中...