大白刷题录

UVa 11729

排序，贪心

这个题目很有价值。

一方面通过数学推导得出结论。

编号为i的人初始有$A_i$枚金币。对于1号，给了4号$x_1$枚金币，自己还有$A_1-x_1$枚。然后从2号拿走$x_2$枚金币，现在有$A_1-x_1+x_2$枚金币，另外，设平均金币值为$A_1-x_1+x_2=M$。

由此可类推得到

$A_n-x_n+x_1 \Rightarrow x_n=M-A_n+x_1=x_n-C_n$

我们可以得到类推公式

$$C_i = C_{i-1} + A_i – M $$

证明:

$$x_2 = x_1 – C_1$$

$$x_3 = M-A_2+x_2 =2M-A_1-A_2+x_1=x_1-C_2$$\

以此类推。

可以求得，需要求的结果为:

$$|x_1|+|x_1-C_1|+|x_1-C_2|….|x_1-C_n-1|$$

即求这个式子值最小，即求$C_1, C_2, …C_n$的中位数。

这个题目也是比较有水平

使用了按比例缩小的技巧。其中，按逆时针编号，固定一个点作为原点，建立新坐标。原来的位置呈现在新坐标的位置为$pos = i/n*(n+m)$，如此，求移动距离则是$fabs(pos – floor(pos+0.5))/(n+m)$

蓝桥杯去年山东省的初赛题目，的确有点意思= =

转换方向可以不必在意，因为最终看到的结果已经不知道最初的蚂蚁是哪一只了，所以不用纠结方向的问题。主要要考虑的是最终的位置，以及最初蚂蚁位置的存储，before，after的对应关系。