警示后人,这几道多倍经验错一两个测试点的可能原因
查看原帖
警示后人,这几道多倍经验错一两个测试点的可能原因
578590
Inui_Sana楼主2023/1/31 21:36

这道题的 cmp 挺坑的。如果是分析 ai,bia_i,b_i 的关系进行排序的话,这种写法是错误的:(我是重载<写法)

if(tmp.b<tmp.a&&b>a){
	return true;
}
if(tmp.b>tmp.a&&b<a){
	return false;
}
if(a>b){
	return b>tmp.b;
}
return a<tmp.a;

甚至这样还是错的:

if(a<b){
	if(tmp.a<tmp.b){
		return a<tmp.a;
	}else{
		return true;
	}
}else{
	if(tmp.a>tmp.b){
		return b>tmp.b;
	}else{
		return false;
	}
}

具体原因大概是这两种方式都会导致不稳定的排序。所以要这么写:

if(a==b){
	return tmp.a>tmp.b;
}
if(a<b){
	if(tmp.a<tmp.b){
		return a<tmp.a;
	}else{
		return true;
	}
}else{
	if(tmp.a>tmp.b){
		return b>tmp.b;
	}else{
		return false;
	}
}
2023/1/31 21:36
加载中...