求问单调队列的 hd&tl 问题
查看原帖
求问单调队列的 hd&tl 问题
838570
Double_Sheep楼主2024/11/26 15:46

rt,请问下面的两份代码有啥区别?

区别只有 hdhd 的初值与 while 循环的判定条件(hd<tlhd<tl or hdtlhd\le 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

2024/11/26 15:46
加载中...