rt,请问下面的两份代码有啥区别?
区别只有 hd 的初值与 while 循环的判定条件(hd<tl or hd≤tl)。
int hd = 0, tl = 0;
for (int i = 1; i <= n; i++) {
while (hd < tl && (f[q[hd + 1]] - f[q[hd]]) <= (s + st[i]) * (sc[q[hd + 1]] - sc[q[hd]])) hd++;
f[i] = f[q[hd]] + st[i] * (sc[i] - sc[q[hd]]) + s * (sc[n] - sc[q[hd]]);
while (hd < tl && (f[q[tl]] - f[q[tl - 1]]) * (sc[i] - sc[q[tl]]) >= (f[i] - f[q[tl]]) * (sc[q[tl]] - sc[q[tl - 1]])) tl--;
q[++tl] = i;
}
int hd = 1, tl = 0;
for (int i = 1; i <= n; i++) {
while (hd <= tl && (f[q[hd + 1]] - f[q[hd]]) <= (s + st[i]) * (sc[q[hd + 1]] - sc[q[hd]])) hd++;
f[i] = f[q[hd]] + st[i] * (sc[i] - sc[q[hd]]) + s * (sc[n] - sc[q[hd]]);
while (hd <= tl && (f[q[tl]] - f[q[tl - 1]]) * (sc[i] - sc[q[tl]]) >= (f[i] - f[q[tl]]) * (sc[q[tl]] - sc[q[tl - 1]])) tl--;
q[++tl] = i;
}
谢谢QAQ