Description:

度度熊很喜欢数组！！

我们称一个整数数组为稳定的，若且唯若其同时符合以下两个条件：

  1. 数组里面的元素都是非负整数。
  2. 数组里面最大的元素跟最小的元素的差值不超过 1。

举例而言，[1,2,1,2] 是稳定的，而 [−1,0,−1] 跟 [1,2,3] 都不是。

现在，定义一个在整数数组进行的操作：

  • 选择数组中两个不同的元素 a 以及 b，将 a 减去 2，以及将 b 加上 1。

举例而言，[1,2,3] 经过一次操作后，有可能变为 [−1,2,4] 或 [2,2,1]。

现在给定一个整数数组，在任意进行操作后，请问在所有可能达到的稳定数组中，拥有最大的『数组中的最小值』的那些数组，此值是多少呢？

Input:

输入的第一行有一个正整数 T，代表接下来有几组测试数据。

对于每组测试数据：
第一行有一个正整数 N。
接下来的一行有 N 个非负整数 xi，代表给定的数组。

  • 1≤N≤3×105
  • 0≤xi≤108
  • 1≤T≤18
  • 至多 1 组测试数据中的 N>30000

Output:

对于每一组测试数据，请依序各自在一行内输出一个整数，代表可能到达的平衡状态中最大的『数组中的最小值』，如果无法达成平衡状态，则输出 −1。

Sample Input:

2
3
1 2 4
2
0 100000000

Sample Output:

2
33333333

题目链接

题目要找进行操作后数列中的最大的最小值，此时可以二分结果，对每一个二分出来的结果进行判断是否可以通过操作使此结果为数列中的最小值，判断方式为统计将比二分结果小的数通过操作加上来所需要减去的数量，判断比二分结果大的数是否可以满足加上来的需要。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define XDebug(x) cout<<#x<<"="<<x<<endl;
#define ArrayDebug(x,i) cout<<#x<<"["<<i<<"]="<<x[i]<<endl;
#define print(x) out(x);putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
template <class T>
inline bool read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) {
        return 0;
    }
    while (c != '-' && (c < '0' || c > '9')) {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return 1;
}
template <class T>
inline void out(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        out(x / 10);
    }
    putchar(x % 10 + '0');
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	ll T;
	read(T);
	for (ll Case = 1, N; Case <= T; ++Case) {
		read(N);
		vector<ll> Ary(N);
		for (ll i = 0; i < N; ++i) {
			read(Ary[i]);
		}
		// 二分结果
		ll Left = 0, Right = INF;
		while (Left <= Right) {
			ll Mid = (Left + Right) / 2;
			ll temp = 0;
			for (int i = 0; i < N; ++i) {
				// 若Ary[i]>Mid，则Ary[i]可提供一次-2操作
				if (Ary[i] > Mid) {
					temp += (Ary[i] - Mid) / 2;
				}
				// 否则Ary[i]需要增加到Mid
				else {
					temp += Ary[i] - Mid;
				}
			}
			// 最小值可以达到Mid或以上
			if (temp >= 0) {
				Left = Mid + 1;
			}
			// 最小值无法达到Mid
			else {
				Right = Mid - 1;
			}
		}
		print(Right);
	}
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("gedit out.txt");
#endif
    return 0;
}