试题 算法提高 游览计划_python 试题 算法提高 游览计划

资源限制

内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

问题描述

　　在一条笔直的公路上有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。

思路：

数学公式推导，假如 现在有4个点 距离分别为1 3 5 7，存入数组下标1~4

那么在数轴上，加上起点，是 0 1 3 5 7

由于每次出发均是由起点0出发，所以0点需特殊判断，我们先分析除0点外其他点。

对于每个 ai 和 aj，我们判断其相邻情况，对于例子1 3 5 7，我们求3 和 7的相邻总情况，可以先把3拿出来，对于剩余 n-1 个数全排列，共有(n-1)!种情况，然后我们再把 3 插入到7的左边或者右边，共两种情况，即2*(n-1)!，所有每对ai 和 aj的贡献为*2*(n-1)!

再来分析起点，我们先拿出起点连接的下一个数，对于剩余n-1个数全排列，再把拿出点放入起点后，总体即为(n-1)!，然后即可得 起点的贡献为 *(n-1)!

又知道整体概率为 n!，所以最终推出 （*2*(n-1)!+ *(n-1)!）/ n!

即*2+ai ) )/n，最后再利用gcd将分子分母化为最简即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e6+10;
int n,a[MAXN];
ll x,y;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        x+=a[i];
        for(int j=i+1;j<=n;j++) 
            x+=2*(a[j]-a[i]);
    }
    y=n;
    int t=__gcd(x,y);
    x/=t;y/=t;
    cout<<x<<" "<<y;
    return 0;
}