思路 > 对于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; } ```

``` #include<bits/stdc++.h> using namespace std; #define ll long long const int N=1e5+10; ll n,k,T; ll a[N],b[N],aa[N],s1[N],s2[N]; bool check(ll n){ for(int i=1;i<=n;i++)b[i]=a[i]; sort(b+1,b+n+1); for(int i=1;i<=n;i++){ s1[i]=s1[i-1]+b[i]; s2[i]=s2[i-1]+b[i]*b[i]; } for(int i=1,e=k;e<=n;e++,i++){ if(k*(s2[e]-s2[i-1])-(s1[e]-s1[i-1])*(s1[e]-s1[i-1])<k*k*T){ return true; } } return false; } int main(){ cin>>n>>k>>T; for(int i=1;i<=n;i++)cin>>a[i]; ll 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))cout<<-1; else cout<<l; return 0; } ```