Meaning Mean

---

题型分析

简单数论

题目描述&数据范围

对一个长度为 $n$ 的数组 $a$ 进行如下操作：

• 每次选择两个不同的数 $a_i,a_j$ 删除这两个数并且在数组的末尾加入 $\lfloor \frac{(a_i+a_j)}{2}\rfloor$

重复这个操作直到 $a$ 中只剩下一个数，求最后剩下的数的最大值

数据保证：

$1\le n\le 50$

$1\le a_i\le 10^9$

题解

每次操作越大的数对答案的贡献度损失越大，可以贪心的从最小的数开始操作

排个序就能解决

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(){
	int n;cin>>n;
	vector<ll>a(n+1);
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	sort(a.begin()+1,a.end());
	ll sum=0;
	for(auto v:a){
		if(!sum)sum=v;
		else sum=(sum+v)/2;
	}
	cout<<sum<<'\n';
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    /fstream in("in.txt",ios::in);cin.rdbuf(in.rdbuf());
	int T=1;cin>>T;
	while(T--)solve();
}