题目大意：有n堆怪物，每堆怪物有a[i]只怪，有两种攻击，每次普攻费用为1，杀死任意一只怪物，同时为大招积攒一点能量，施放大招时可以消耗所有能量，选择一堆怪物杀死等于消耗能量数的怪物，放一次大招费用为1，问杀死所有怪物需要的最小操作次数是多少
1<=n<=2e5;1<=a[i]<=1e9
思路：因为大招可以花一点费用杀死很多怪，性价比肯定比普攻高，且大招一次消耗的能量越多越赚，要消耗更多的能量就要选择怪的数量尽可能多的堆施放大招，所以我们按怪的数量从小到大排序，建立双指针l=1,r=n，前面怪数量少的我们用普攻，如果当前积攒的能量达到a[r]了，就用大招消灭a[r]，这样最终可能会剩余1堆，那么除去当前大招能杀死的以外，其他的一半向上取整都要用普攻，然后其余的一个大招杀掉。
//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
ll a[N];
int n;
void init()
{
}
void solve()
{
cin >> n;
init();
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a + 1, a + n + 1);
ll l = 1, r = n, x = 0;
ll ans = 0;
while (l < r)
{//直到剩余一堆或0堆
if (a[l] + x < a[r])
{//当前能量不够放大招
x += a[l];//这堆全部普攻解决
ans += a[l];
l++;
}
else
{//当前能放大
ans += a[r] - x;//用普攻凑齐剩下需要的能量
a[l] -= a[r] - x;
ans++;//放一次大
r--;
x = 0;
}
}
if (a[l])
{//还剩一堆
ll temp = (a[l] - x) / 2;//除去已经积攒的能量以外的一半要用普攻
ans += temp;
a[l] -= temp;
x += temp;
if (x)
{//可以放一次大
a[l] -= x;
ans++;
}
if(a[l])
ans++;
}
cout << ans;
cout << '\n';
}
int main()
{
int t;
cin >> t;
while (t--)
{
solve();
}
}