codeforces_A. Salem and Sticks_数组/暴力

Salem gave you a1,a2,…,an.

For every stick, you can change its length to any other positive integer length (that is, either shrink or stretch it). The cost of changing the stick's length from x.

A stick length |ai−t|≤1.

Salem asks you to change the lengths of some sticks (possibly all or none), such that all sticks' lengths are almost good for some positive integer t is not fixed in advance and you can choose it as any positive integer.

As an answer, print the value of t, print any of them.

Input

The first line contains a single integer 1≤n≤1000) — the number of sticks.

The second line contains 1≤ai≤100) — the lengths of the sticks.

Output

Print the value of t, print any of them.

Examples
input
Copy
3
10 1 4
output
Copy
3 7
input
Copy
5
1 1 2 2 3
output
Copy
2 0

Note

In the first example, we can change t=3.

In the second example, the sticks lengths are already almost good for t=2, so we don't have to do anything.

 1 #include <bits/stdc++.h>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 int n;
 7 int a[1005];
 8 int sum=0;
 9 
10 int cal(int k){
11     int res=0;
12     for(int i=0;i<n;i++){
13         if(abs(a[i]-k)>1){
14             res+=(abs(a[i]-k)-1);
15         }
16     }
17     return res;
18 }
19 
20 int main()
21 {
22     int minn=99999999;
23     int maxx=0;
24     scanf("%d",&n);
25     for(int i=0;i<n;i++){
26         scanf("%d",&a[i]);
27         sum+=a[i];
28         minn=a[i]<minn?a[i]:minn;
29         maxx=a[i]>maxx?a[i]:maxx;
30     }
31     int r1=1;
32     int cost=99999999;
33     int now=0;
34     for(int i=minn;i<=maxx;i++){
35         now=cal(i);
36         if(now<cost){
37             r1=i;
38             cost=now;
39         }
40     }
41     printf("%d %d
",r1,cost);
42     /*
43     int r1=sum/n;
44     int r2=r1+1;
45     int _r1=cal(r1,a);
46     int _r2=cal(r2,a);
47 
48     if(_r1<_r2){
49         printf("%d %d
",r1,_r1);
50     }else{
51         printf("%d %d
",r2,_r2);
52     }
53     */
54 
55     return 0;
56 }

View Code

codeforces_A. Salem and Sticks_数组/暴力

相关推荐