Codeforces Round #198 (Div. 2) —

C题很容易看懂题目，不过两个循环肯定会TLE，所以得用点小聪明；

首先排好序，因为是全排列，乱序和顺序的结果是一样的；

然后呢····

如果是数列 1 2 3 4 5

元素1 被 2 3 4 5每个减了2次，它自己减0一次；相抵后为-7；

元素2 被 3 5 4 每个减了2次，它减1两次，减0一次；相抵后为 -3；

元素3 相抵后为1；

可以发现他们的数量相差4；这样就好办了，一个循环就搞定了；

代码：

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 int a[];

 long long gcd(long long a,long long b)

 {

     return b==?a:gcd(b,a%b);

 }

 int main()

 {

     long long ans=,n,t;

     cin>>n;

     for(long long i=; i<n; i++)

         scanf("%d",&a[i]);

     sort(a,a+n);

     t=-*n;

     for(long long i=; i<n; i++,t+=)

         ans+=a[i]*t;

     long long k=gcd(ans,n);

     cout<<ans/k<<" "<<n/k<<endl;

     return ;

 }

巴特西

Codeforces Round #198 (Div. 2) —— C

最新文章

热门文章