如题,前两个 subtask 调过了,但 subtask #2 附加数据过了,前三个点寄了。
核心代码:
int T;
int n, q;
long long arr[100010];
long double avg[100010];
long double min_delta[100010];
int main()
{
read(T);
while (T--)
{
read(n), read(q);
for (int i = 1; i <= n; ++i)
{
arr[i] = read();
}
sort(arr + 1, arr + 1 + n, [](long long x, long long y)
{
return x > y;
});
for (int i = 1; i <= n; ++i)
{
avg[i] = (long double)(avg[i - 1] * (i - 1) + arr[i]) / (long double)i;
}
min_delta[n + 1] = 1e15;
for (int i = n; i >= 1; --i)
{
min_delta[i] = min(min_delta[i + 1], avg[i] - arr[i]);
}
for (int i = 1; i <= q; ++i)
{
long double input = read();
int pos = upper_bound(min_delta + 1, min_delta + 1 + n, input) - (min_delta + 1);
printf("%d ", pos);
}
puts("");
}
return 0;
}
可以确保
read()
没有问题()