首页 > 代码库 > E: Translate

E: Translate

题目描述

你N个正整数a[1]...a[N],在最初的时候,你选择一个正整数X,然后以后每一步,你可以使一个数a[i] 变成 a[i] + X,或者 a[i] - X,聪明的你,一定会知道怎么选择这个X,使得最后所有的数都变成相等,而且使用的变化步数最少。

输入

多组测试数据。对于每组数据,一个N(2 <= N <= 1000),接下来一行有N个数a[1]...a[N] (1 <= a[i] <= 10^6)。

保证这N个数不全相等。

输出

每组数据单独一行,你找出的正整数X,以及最少步数,两个数用一个空格隔开.

 

样例输入

3
1 2 3
4
3 5 7 11

样例输出

1 2
2 5
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 
 7 int GCD(int a,int b)
 8 {
 9     if(b==0)
10         return a;
11     else
12         return GCD(b,a%b);
13 } 
14 int LCM(int a,int b)
15 {
16     int gcd=GCD(a,b);
17     return (a*b)/gcd;
18 }
19 int main()
20 {
21     int n;
22     while(scanf("%d",&n)!=EOF)
23     {
24         int a[1010];
25         int b[1010];
26         for(int i=1;i<=n;i++)
27         {
28             scanf("%d",&a[i]);
29             
30         }
31         sort(a+1,a+1+n);
32         int q=a[(n+1)/2];
33         int gcd;
34         int ans=0;
35         for(int i=1;i<=n;i++)
36         {
37             b[i]=abs(q-a[i]);
38             if(i==1)
39                 gcd=b[i];
40             if(i>=2&&i!=(n+1)/2)
41                 gcd=GCD(gcd,b[i]);
42         }
43         for(int i=1;i<=n;i++)
44         {
45              ans+=abs(a[i]-q)/gcd;
46         }
47         printf("%d %d\n",gcd,ans);
48     }
49     return 0;
50 } 

 

E: Translate