不会。。

不懂楼下的是什么意思。。

这个题目没有什么好说的。但是如果是不要求士兵相临又应该怎么办？等大牛回答。

解法描述

由于是求曼哈顿距离，所以可以将x, y分量分开考虑。

y: 要将所有的yi集中到某个y0上。

可以通过微量法证明y0一定在某个已知yi上。再通过微量法证明y0一定是yi的中位数。

x: 要将所有的x1集中到某个x0。其他xi依次相间1排下去。

先将x排序，可以证明x的顺序一定就是最终的序列的顺序（因为交叉位置的话解更差）。

由于定了序，所以有xi = x0 + i - 1，则可以将问题转化为x'i = xi - (i - 1) = x0。

x'就是与y同样的问题了，求xi - (i - 1)的中位数x0就可以了。

本资料由Amber大牛提供··

厉害！大牛！

崇拜！

3次QSORT就过了。

没有难度！

终于明白是咋一回事了，再次膜拜Amber神牛，黑书75页~~~~~~原题啊

这题无敌了，4遍qsort

黑书75页

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案错误...　├ 标准行输出8640 ├ 错误行输出 8990

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0m

为什么第六个点错误呢？

非常怀疑这个点的合法性

好简单的一道题。。。。

我随便枚举一下x,y都过了……

不懂

不太理解

为什么奇数时中位数一定是x[(n+1)/2]

而不是(x[(n+1)/2+1]+x[(n+1]/2])/2?

Y[i]求中位数

x【i】就比较囧了

设x上是以x0为中点的

那x【i】=x0+1-i;

对每一个x【i】有一个x0【i】

那么一定是也是中位数嘞

——————————————————————

程序3次快排 ，，吃得消 ，，没话说了