重庆微网站制作,漳州北京网站建设公司哪家好,长春服务好的网站建设,电商平台建设费用成绩统计 问题描述格式输入格式输出样例输入样例输出评测用例规模与约定解析参考程序难度等级 问题描述 题目有问题方差定义那加平方#xff08;vi-v#xff09; 格式输入
输入的第一行包含三个正整数n,k,T #xff0c;相邻整数之间使用一个空格分隔。 第二行包含n个正整数… 成绩统计 问题描述格式输入格式输出样例输入样例输出评测用例规模与约定解析参考程序难度等级 问题描述 题目有问题方差定义那加平方vi-v 格式输入
输入的第一行包含三个正整数n,k,T 相邻整数之间使用一个空格分隔。 第二行包含n个正整数a1,a2,··· ,an 相邻整数之间使用一个空格分隔 格式输出
输出一行包含一个整数表示答案。如果不能满足条件输出−1 样例输入
5 3 1 3 2 5 2 3 样例输出
4 评测用例规模与约定
对于10%的评测用例保证1≤n,k≤10^2 对于30%的评测用例保证1≤n,k≤10^3 对于所有评测用例保证1≤n,k≤10^5 1≤T ≤2^31−11≤ai≤n 。 解析
二分可过全部不用暴力只能30% 参考程序
#includealgorithm
#includeiostream
using namespace std;
typedef long long ll;
const int N100010;
__int128 k,T;
ll a[N];
__int128 b[N];
__int128 s1[N],s2[N];
bool check(int m)
{for(int i1;im;i)b[i]a[i];sort(b1,bm1);for(int i1;im;i){s1[i]s1[i-1]b[i];s2[i]s2[i-1]b[i]*b[i];}__int128 limk*k*T;for(int ik;im;i){__int128 sumk*(s2[i]-s2[i-k])-(s1[i]-s1[i-k])*(s1[i]-s1[i-k]);//推公式if(sumlim){return true;}}return false;
}
int main()
{int n;long long k1,T1;cinnk1T1;kk1,TT1;for(int i1;in;i)cina[i];int lk-1,rn1;while(l1r){int mid(lr)/2;if(check(mid))rmid;else lmid;}cout(rn?r:-1);return 0;
}难度等级
⭐️⭐️⭐️⭐️1~10星想完全过还是挺难的
以个人刷题整理为目的如若侵权请联系删除~
