江苏省建设工程设计施工图审核中心网站,湖北专业网站建设维修电话,wordpress内置函数大全,展览网站模板题干#xff1a;
若x1,x2,x3……xn的平均数为k。 则方差s^2 1/n * [(x1-k)^2(x2-k)^2…….(xn-k)^2] 。 方差即偏离平方的均值#xff0c;称为标准差或均方差#xff0c;方差描述波动程度。 给出M个数#xff0c;从中找出N个数#xff0c;使这N个数方差最小。 Input …题干
若x1,x2,x3……xn的平均数为k。 则方差s^2 1/n * [(x1-k)^2(x2-k)^2…….(xn-k)^2] 。 方差即偏离平方的均值称为标准差或均方差方差描述波动程度。 给出M个数从中找出N个数使这N个数方差最小。 Input 第1行2个数M,N(M N, M 10000) 第2 - M 1行M个数的具体值(0 Xi 10000) Output 输出最小方差 * N的整数部分。 Input示例 5 3 1 2 3 4 5 Output示例 2
解题报告 首先想到这题肯定是要排序的方差就是稳定程度嘛肯定相邻的两个数好过不相邻的两个数然后我们进行公式化简 因为我们知道数据范围是1e4所以n^2的复杂度虽然也可以但是我们还有更优秀的nlogn的方法排序用去了nlogn所以其他的部分最好在o(n)内完成。而我们观察原公式后发现如果直接求的话那每一次遍历都需要o(m)求一遍k那就又成o(nm)复杂度了和n^2是一个数量级的肯定不行所以我们考虑用这一条性质巧妙的把k约掉发现得出的这两项刚好满足前缀和类性质于是可以o(1)查询了然后o(n-m)遍历一遍就可以出答案了。 下面上代码
#includebits/stdc.h
#define ll long long
using namespace std;
const int MAXN 1e45;ll a[MAXN], sum[MAXN], summ[MAXN];
int main()
{int n,m;cinnm;for(int i1; in; i) {scanf(%lld,a[i]);}sort(a1, a1n);sum[0] summ[0] 0;for(int i1; in; i) {sum[i] sum[i-1] a[i];summ[i] summ[i-1] a[i]*a[i];}double minn (double)LLONG_MAX;for(int im; in; i) {double tmp (summ[i]-summ[i-m])-1.0*(sum[i]-sum[i-m])*(sum[i]-sum[i-m])/m;minn min(tmp,minn);}printf(%lld\n,(ll)floor(minn));return 0;
}
总结 由此我们也知道不仅是值可以求前缀和任何一个我们想知道的值只要不带更新操作都可以求前缀和。
