警钟长鸣,如果你 WA on #26
查看原帖
警钟长鸣,如果你 WA on #26
1340759
ARIS2_0楼主2025/1/15 19:08

处理 i=1Nxxi\sum\limits_{i=1}^N|x-x_i|i=1Nyyi\sum\limits_{i=1}^N|y-y_i| 时,上下界要开到 2×106-2\times 10^62×1062\times 10^6

因为对于式子 i=1NyyiDi=1Nxxi\sum\limits_{i=1}^N|y-y_i|\le D-\sum\limits_{i=1}^N|x-x_i|,有可能 D=i=1Nxxi=106D=\sum\limits_{i=1}^N|x-x_i|=10^6i=1Nyyi=0\sum\limits_{i=1}^N|y-y_i|=0,此时 i=1Nxxi=106\sum\limits_{i=1}^N|x-x_i|=10^6 在极限情况下要有 x=2×106x=2\times 10^6x=2×106x=-2\times 10^6 才能取到。

2025/1/15 19:08
加载中...