85分蜜汁WA三个点求助

P4383 [八省联考 2018] 林克卡特树

```cpp return now.x-1ll*mid*k; ``` 改成 ```cpp return now.x-1ll*mid*now.y; ``` ~~我才不会告诉你我也错在这儿~~
by WAPER4EVER @ 2019-08-13 16:06:01


@[WAPER420](/user/72419) 这是为啥呀。。。
by Treaker @ 2020-06-18 19:43:02


@[Treaker](/user/153898) 我这都多久回答的了。。早忘了qaq
by WAPER4EVER @ 2020-06-18 20:00:53


@[WAPER420](/user/72419) 想想呗
by Treaker @ 2020-06-18 20:05:45


@[Treaker](/user/153898) 这个问题比较显然,建议重新看看您学wqs二分的那博客,如果找到的文章不那么差都会讲这个问题
by tommy0221 @ 2020-07-27 18:24:13


@[WAPER4EVER](/user/72419) 我按照你的方法改了被 LOJ 数据叉了。
by 5ab_juruo @ 2023-03-04 16:52:42


@[5ab_juruo](/user/119491) 我的天哪。三年了还回复啊。我高一做的题这会儿都大一了。 马上我看一下吧。
by WAPER4EVER @ 2023-03-04 18:05:22


@[5ab_juruo](/user/119491) 首先,我三年前讲错了,输出的答案就应该是 $-k \times mid $ 而非 $-now.y \times mid$。 其次,注意你的二分要与你在值相同时求边数最小/边数最大要保持一致。 例如我的二分是这样的: ``` ll l=-inf,r=inf,ans=0; while(l<=r) { ll mid=(l+r)>>1; if(check(mid)<=k){ans=mid;r=mid-1;} else l=mid+1; } ``` 那么这样的话在值相同时我应该求边数最小的方案。 但是我在原代码里求了边数最大的方案,所以导致了将 $-k \times mid $ 改为 $-now.y \times mid$ 就过了(这应该是一个巧合)。 如果你 AC 了该题却被 hack 掉了,注意一下我上面说的这个问题。
by WAPER4EVER @ 2023-03-04 18:25:43


哎呀好像甚至不是高一做的,初三做的。。
by WAPER4EVER @ 2023-03-04 18:26:45


@[WAPER4EVER](/user/72419) 之前一直没搞懂为什么 wqs 有时候按最小有时候按最大的,帮大忙了,感谢 ~~这会您都大二了吧~~
by CarroT1212 @ 2023-12-26 15:39:02


|