蓝桥杯 游览计划 （Python实现）_旅游线路自动规划设计程序 python

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

　　在一条笔直的公路上有n个景点，第i个景点在Ai千米处，起点在0千米处，所有景点都位于起点一侧。
　　八云紫（咦这是怎么中枪的？）从起点出发，每次任选一个没有游览的景点，从当前位置出发到达那个景点游览，这样进行n次，直到停在最后游览的那个景点。（最后不会回到起点。）
　　在x千米处的点与在y千米处的点的路程为|x-y|千米。八云紫平均的总游览路程是多少？（她选择所有游览路线的概率是相等的，你可以认为这个概率等于1/n!。）

输入格式

　　第一行一个数n，第二行n个数A1, A2 ... An，如题目所述。

输出格式

　　输出一行，两个数，答案的分子和分母。要求分子分母不能再约分。

样例输入

3
2 3 5

样例输出

22 3

数据规模和约定

　　2<n<100000，1≤Ai<10^7，对于任意1≤i<n，都有Ai<A(i+1)。

样例说明

　　可能的游览顺序与对应的总路程：
　　[2, 3, 5]: |2 – 0| + |3 – 2| + |5 – 3| = 5;
　　[2, 5, 3]: |2 – 0| + |5 – 2| + |3 – 5| = 7;
　　[3, 2, 5]: |3 – 0| + |2 – 3| + |5 – 2| = 7;
　　[3, 5, 2]: |3 – 0| + |5 – 3| + |2 – 5| = 8;
　　[5, 2, 3]: |5 – 0| + |2 – 5| + |3 – 2| = 9;
　　[5, 3, 2]: |5 – 0| + |3 – 5| + |2 – 3| = 8.

　　平均路程：(5+7+7+8+9+8)/6 = 22/3。

        本题乍一看，似乎要计算很大的数字又或是要循环很多次。但是其实拆解一下就会发现其实很简单没那么复杂（关键是拆解绝对值的时候找规律）。

        首先，我们可以把以上所有绝对值的和看成两类，一类是a[i]之间相减(例如3 - 2， 5 - 3), 另外一类是与原点的距离（例如2 - 0， 3 - 0）。计算算第一类的时候，我们发现其实有很多的重复的量，比如说3 - 2和2 - 3，去绝对值后都是一样的，所以我们先去其中的不重复的一组，然后再计算有多少相同的组即可。拿出一组来分析时，容易想到第一个数在计算的时候要被后面的所有的数减一遍(数组按顺序排列，所以第一个数一定是最小的，取绝对值的时候前面一定是负号)，而最后的一个数也要减去前面所有的数一遍，这个时候我们就有了(n - 1)a[n], 和负的(n - 1)[a[1]，前面的系数都是n - 1。继续，到a[2], 这时会有一个a[2] - a[1], 以及a[i] - a[2](2 < i <= n), 所以会减掉n - 3 个a[2], 同理会加上n - 3个a[n - 1]......，依次类推可以得到所有的和s1。

                                    

        再来看有多少个s1，其实也就是看当两个数凑在一起的时候有多少种排列方式。比如样例中的3,5两个点，只要这两个点在游览的时候是紧接着的，就一定会有一个5 - 3出现，而且此时5和3可以调换位置（因为要取绝对值）。而由排列组合的知识知道两个数紧挨在一起时的排列方式有(n - 1) ! 种（也就是n - 1个元素进行全排列），而再加上可以调换顺序还需要乘以2，则第一类的和为2(n - 1) ! s1。

        接下来第二类就很容易了，首先看样例很容易发现2 - 0，3 - 0， 5 - 0 都有两个，实际上只要固定一个数在第一个，而后有几种排列方式就有几个a[i] - 0(1<= i <= n), 也就是有几倍数列的和，计算一下便知道有(n - 1)!种排列，也就是s2  = (n - 1)! * sum(a)。注意到没有？s = s2 + 2(n - 1) ! s1 = (n - 1)! (sum(a)+2s1).

        而总的排列方式为n!，一除就只剩下了一个n(都含有一个(n - 1) ! ), 而分子就只剩下了(sum(a)+2s1)。大功告成！至于怎么得到最后的结果，也就是化简到不能再约分。只要把每一个数除以最大公约数即可。接下来上代码：

def simplify(a, b):
    while a % b:
        t = a % b
        a, b = b, t
    return b
 
 
n = int(input().rstrip())
a = [int(i) for i in input().rstrip().split(' ')]  # 表示每一个景点的位置
s2, s1, count = sum(a), 0, 0  # count用来表示元素的下标
for i in range(n - 1, -1, -2):   # 步长为2，(下限设置为0也可以，加上一个0等于没加)
    s1 += i * (a[n - 1 - count] - a[count])
    count += 1
x, f = 2 * s1 + s2, n  # 直接利用推导的结论
m = simplify(x, f)
print(x // m, f // m)