問題描述

題目有問題方差定義那加平方（vi-v）

---

格式輸入

輸入的第一行包含三個(gè)正整數(shù)n,k,T ，相鄰整數(shù)之間使用一個(gè)空格分隔。
第二行包含n個(gè)正整數(shù)a1,a2,··· ,an ，相鄰整數(shù)之間使用一個(gè)空格分隔

---

格式輸出

輸出一行包含一個(gè)整數(shù)表示答案。如果不能滿足條件，輸出?1

---

樣例輸入

5 3 1
3 2 5 2 3

---

樣例輸出

4

---

評測用例規(guī)模與約定

對于10%的評測用例，保證1≤n,k≤10^2 ；
對于30%的評測用例，保證1≤n,k≤10^3 ；
對于所有評測用例，保證1≤n,k≤10^5 ，1≤T ≤2^31?1，1≤ai≤n 。

---

解析

二分可過全部，不用暴力只能30%；

---

參考程序

#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=100010;
__int128 k,T;
ll a[N];
__int128 b[N];
__int128 s1[N],s2[N];
bool check(int m)
{for(int i=1;i<=m;i++)b[i]=a[i];sort(b+1,b+m+1);for(int i=1;i<=m;i++){s1[i]=s1[i-1]+b[i];s2[i]=s2[i-1]+b[i]*b[i];}__int128 lim=k*k*T;for(int i=k;i<=m;i++){__int128 sum=k*(s2[i]-s2[i-k])-(s1[i]-s1[i-k])*(s1[i]-s1[i-k]);//推公式if(sum<lim){return true;}}return false;
}
int main()
{int n;long long k1,T1;cin>>n>>k1>>T1;k=k1,T=T1;for(int i=1;i<=n;i++)cin>>a[i];int l=k-1,r=n+1;while(l+1<r){int mid=(l+r)/2;if(check(mid))r=mid;else l=mid;}cout<<(r<=n?r:-1);return 0;
}

難度等級

????????（1~10星）想完全過還是挺難的

以個(gè)人刷題整理為目的，如若侵權(quán)，請聯(lián)系刪除~