Gym - 101778B Ran and the Lock Code
题意
让你构造n个数，它们的平均数要是a，求构造的数列最多有多少个不同的数。
思路
我花了很长时间才克服了一个思维定式：
首先很容易想到，(1 leftrightarrow 2a-1)对称分布的数字是都可以的，所以，(nleq2a-1)的答案就是(n)，大于的就是(2a-1)。
然后看以下样例，没问题，就这么写了然后就wa了。
为什么呢？可以这样考虑，(n)比较大的时候：$${1,cdots, a-1, a ,a+1,cdots ,2a-1,cdots ??? }$$
一个关键点在于，右边还有(n-(2a-1))个位置，这里填什么？
全填(a)?，但是如果填入({ 1,a-1,2a }) 可以发现，平均数不会变，但是多了一个新的数，({ 2a })
也就是说后面这几个位置怎么安排是一个很复杂很抽象的问题，那我们想一下如何验证某个情况可不可行。
假设当前我猜可以构造出的不同数有(m)个，为了数字尽可能多，肯定要包括({1cdots m})
显然(m=2a-1)时候就是我们之前想的非常理想的情况。
因为平均之后总和要等于(a imes m)所以我们可以这样检测：
[(m+1) imes m div2-a imes m$$就是说这$m$个数总和比全$a$要多出多少，
这些多出来的，我们还剩下$n-m$个数可以去凑，看看能否凑齐就可以了。
于是我们就有个方程，可以验证是单调的，二分来做即可。
## 代码
```cpp
#include <bits/stdc++.h>
#define _debug(x) cerr<<#x<<" = "<<(x)<<endl;fflush(stdout)
#define cvint const vint &
#define cint const int &
using namespace std;
typedef long long ll;
typedef vector<int> vint;
const int maxn = 505;
const int inf = 0x3F3F3F3F;
const int mod = 1e9 + 7;
int Kase;
int n, a, ans;
inline bool chek(const ll &m) {
// return (m + 1) * m / 2 - m * a <= (n - m) * (a - 1);
return 2ll * n - m <= 2ll * a * n - m * m;
}
int main() {
scanf("%d", &Kase);
while (Kase--) {
scanf("%d %d", &n, &a);
if (n <= 2 * a - 1) {
printf("%d
", n);
continue;
}
int l = 1, r = n, m;
while (l <= r) {
m = l + r >> 1;
if (chek(m)) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
printf("%d
", ans);
}
return 0;
}
/*
9
1 2 8 3 7 4 1 2 5
*/
```]