思路
> 对于n个数选择k个数，使得选出的k个数方差最小。那么可以证明：序列排序后，某连续的k个数可以使得方差最小。答案就呼之欲出了使用二分法求解
> 时间复杂度$O(nlog^2n)$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100010;
int n, k, T;
int a[N], b[N];
bool check(int x)
{
for (int i = 1; i <= x; i++) b[i] = a[i];
sort(b + 1, b + 1 + x);
ll sum = 0, v = 0;
for (int i = 1; i < k; i++)
{
sum += (ll)b[i] * b[i];
v += b[i];
}
for (int i = k; i <= x; i++)
{
sum += (ll)b[i] * b[i] - (ll)b[i - k] * b[i - k];
v += b[i] - b[i - k];
double t = 1.0 * v / k;
if ((sum - 1.0 * v * v / k) / k < T)
{
//cout<< (sum - 1.0 * v * v / k) / k << endl;
return true;
}
}
return false;
}
int main()
{
scanf("%d%d%d", &n, &k, &T);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int l = k, r = n, mid;
while (l < r)
{
mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (r == n && !check(n)) puts("-1");
else printf("%d", r);
return 0;
}
1 回复
0 转发
2 喜欢
13 阅读
