警示后人 - 可删堆
查看原帖
警示后人 - 可删堆
1030875
born_to_sun楼主2024/10/21 16:50

如果你使用了可删堆,并且重载了小于号和等号。

重载小于号时,除了比较等效节点的权值大小外,还要对其他每个结构体元素进行大小比较。否则,会在可删堆删除元素时出错。

以下的代码是错误的:

struct no{
	int sum,siz,u;
}c[N];
bool operator <(const no &n1,const no &n2){return n1.sum*n2.siz<n2.sum*n1.siz;}
bool operator ==(const no &n1,const no &n2){return n1.u==n2.u&&n1.sum==n2.sum&&n1.siz==n2.siz;}

因为假设你要删除两个元素,它们的 sum×sizsum\times siz 相等,那么可能会导致你的删除堆和保留堆的堆顶元素不完全相同,这样你无法删掉它,就会出错。

以下的代码是正确的:

struct no{
	int sum,siz,u;
}c[N];
bool operator <(const no &n1,const no &n2){return n1.sum*n2.siz==n2.sum*n1.siz? (n1.sum==n2.sum? n1.u<n2.u: n1.sum>n2.sum): n1.sum*n2.siz<n2.sum*n1.siz;}
bool operator ==(const no &n1,const no &n2){return n1.u==n2.u&&n1.sum==n2.sum&&n1.siz==n2.siz;}
2024/10/21 16:50
加载中...