# PROBLEM LINK:

Practice

Contest: Division 3

Contest: Division 2

Contest: Division 1

**Author:** Jeevan Jyot Singh

**Tester :** Takuki Kurokawa

**Editorialist:** Aman Dwivedi

# DIFFICULTY:

Simple

# PREREQUISITES:

Maths, Observation

# PROBLEM:

You have an array A of length N. You want to divide the array A into two **non-empty** subsets P and Q such that the value of mean(P)+mean(Q) is as large as possible. (Note that each A_i must belong to either subset P or subset Q).

Find this maximum value of mean(P)+mean(Q).

# EXPLANATION:

Letâ€™s put the maximum element of an array in one of the sets say P and the remaining elements in another set Q.

We claim that this division will result in the maximization of mean(P)+mean(Q). Letâ€™s prove:

Suppose we do the first division as above which means set P contains a_1 and the rest of the other elements are in the set Q. Letâ€™s say this value is Sum_1.

Now letâ€™s move one element from set Q to set P. Letâ€™s call it Sum_2

Now if our claim is true, it means Sum_1 > Sum_2

Now as we have said earlier a_1 is the maximum element of the array letâ€™s replace it with the max and all other elements with max-1 since all other elements will be less than max

It means when n>1 then the division which puts the maximum element of an array in one of the sets say P and the remaining elements in another set Q maximizes the value.

When all the elements are equal to max you can see all the divisions will work.

# TIME COMPLEXITY:

O(N) per test case

# SOLUTIONS:

## Author's Solution

```
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
void solve()
{
int n; cin >> n;
int sum = 0, mx = 0;
for(int i = 0; i < n; i++)
{
int x; cin >> x;
mx = max(mx, x);
sum += x;
}
cout << 1.0 * mx + 1.0 * (sum - mx) / (n - 1) << "\n";
}
int32_t main()
{
IOS;
cout << fixed << setprecision(9);
int T; cin >> T;
for(int tc = 1; tc <= T; tc++)
{
solve();
}
return 0;
}
```

## Tester's Solution

```
// tester solution for editorial. please remove this comment section.
#include <bits/stdc++.h>
using namespace std;
int main() {
cout << fixed << setprecision(8);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
}
int mx = 0;
for (int i = 0; i < n; i++) {
mx = max(mx, a[i]);
}
double mean_p = mx;
double mean_q = 1.0 * (sum - mx) / (n - 1);
cout << mean_p + mean_q << '\n';
}
return 0;
}
```

## Editorialist Solution

```
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
int mx = -1;
int sum = 0;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
mx = max(x,mx);
sum+=x;
}
double ans = (double)(sum-mx)/(double)(n-1);
ans += (double)(mx);
cout<<fixed<<setprecision(10)<<ans<<"\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
```