本文共 1256 字，大约阅读时间需要 4 分钟。

问题 D: 统计序列

时间限制: 1 Sec 内存限制: 128 MB

题目描述

有一天， 小Q想起了一个统计公式， 定义一个长度为m的序列，我们可以得到V,V的计算如下： 其中： 现在给你n个整数，需要从中选出m个数，使得他们构成的序列的V值最小。 为了方便，你只需要输出最小的V值乘以m2的值，可以证明这是一个整数。 输入 输入第一行两个正整数n和m。接下来n行，每行一个正整数，表示给你的n个数。 输出 输出一个整数表示答案，保证答案不超过long long int. 样例输入 Copy 5 3 1 2 3 4 5 样例输出 Copy 6 提示 比如选择了1,2,3这3个数，平均数是2，所以V值是，乘上m2后就变成了6。 对于20%的数据，1≤m≤n≤10。 对于50%的数据，1≤m≤n≤1000。 对于100%的数据，1≤m≤n≤100000，给定的n个数的范围是0到10^4。

先化简一下公式吧，因为要求的答案乘m^2，所以直接乘上去即可，让后把x的平均值换进去，经过化简，可得 m * (x1 ^ 2 + x2 ^ 2 + … xm ^ 2) - (x1+x2+…xm) ^ 2 。

先排个序，让后开一个长度为m的窗口依次枚举相邻的m项算出来即可。。至于为什么是相邻的，可能是因为这样方差小？凭感觉猜的。。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105419729 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！