一个关于四边形不等式的问题
查看原帖
一个关于四边形不等式的问题
352328
AdventureExtremeX楼主2023/11/15 00:48

数据:

7
1 0 0 4 0 0 1

在我的程序中,按 len 处理区间答案与最值点

区间 [1,3] 的最值点应当取 2 ,即为先算 [1,2] 在加 [3]

区间 [2,4] 的最值点应当取 2 ,即为先算 [2] 与 [3,4] ,再合并。

那么这个时候根据四边形不等式,区间 [1,4] 的最值点应当在区间 [2,2] 中,但是这组样例显然应该依次把 3,2,1 号点向 4 号点合并,最值点为 3 。

是我理解错了算法,还是有其他处理这个问题的 trick ?

2023/11/15 00:48
加载中...