哈夫曼树，用优先队列实现就可以了
#include<iostream>
#include<queue>
#include<functional>
using namespace std;
const int maxn = 1e4 + 10;
int n, x;
priority_queue<int, vector<int>, greater<int>>q;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)scanf("%d", &x), q.push(x);
int ans = 0;
while (q.size() > 1)
{
int a = q.top();
q.pop();
int b = q.top();
q.pop();
ans = (a + b) / 2;
q.push(ans);
}
ans = q.top();
printf("%d", ans);
return 0;
}
每次选出的两个最小的取平均一定是这个序列中最小的，因为这个平均在最小的两个数之间，一定比其他的要小
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
int a[maxn],n;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
sort(a,a+n);
int ans=a[0];
for(int i=1;i<n;i++)
{
ans=(ans+a[i])/2;
}
printf("%d",ans);
return 0;
}
