#5WA 警示后人
查看原帖
#5WA 警示后人
342185
__builtin_orz楼主2024/8/5 19:47

若数据有解,则每一个蓄水池的水流到的沙漠城市一定是连续的。


但如果无解,有可能不连续。 如果使用线段合并(新的左端点为两条线段左端点的最小值,新的右端点为两条线段右端点的最大值)后再统计,会使可到达的沙漠城市数量增加,(因为中间不连续的城市也加入了计数),即不可到达的沙漠城市数量减小,如这个

3 3
5 3 5
2 2 2
1 9 1

实际上水流总是不能到达9,而合并线段得到的结果却是[1,3]。

所以在搜索的时候就要进行沙漠城市的标记,否则#5WA(比答案小10)

2024/8/5 19:47
加载中...