题解 - 统计序列

题目形貌

有一天， 小Q想起了一个统计公式， 定义一个长度为m的序列，我们可以得到V,V的盘算如下：

其中：

现在给你n个整数，必要从中选出m个数，使得他们构成的序列的V值最小。
为了方便，你只必要输出最小的V值乘以m2的值，可以证明这是一个整数。
输入

输入第一行两个正整数n和m。接下来n行，每行一个正整数，表示给你的n个数。
输出

输出一个整数表示答案，包管答案不高出long long int.
样例

样例输入

5 3
1
2
3
4
5
样例输出

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到1e4。
分析

求V乘m^2的最小值

化简得 m * (x1 ^ 2 + x2 ^ 2 + … xm ^ 2) - (x1+x2+…xm) ^ 2
贪婪，从小到大排序，然后依次算出连续得m个数，取最小值即可
代码

1. #include<bits/stdc++.h>
2.      
3. using namespace std;
4.      
5. typedef long long LL;
6.   
7. const int N = 100000 + 10;
8.   
9. LL n,m;
10. LL a[N],s1[N],s2[N];
11. LL res = 1e18 + 10;
12.   
13. int main(){
14.     ios::sync_with_stdio;
15.     cin.tie(0),cout.tie(0);
16.   
17.     cin >> n >> m;
18.     for(int i = 1;i <= n;i++) cin >> a[i];
19.   
20.     sort(a + 1,a + 1 + n);
21.      
22.     for(int i = 1;i <= n;i++){
23.         s1[i] = s1[i - 1] + a[i];
24.         s2[i] = s2[i - 1] + a[i] * a[i];
25.     }
26.   
27.     for(int i = 1;i <= n - m + 1;i++){
28.         res = min(res,m * (s2[i + m - 1] - s2[i - 1]) - (s1[i + m - 1] - s1[i - 1]) * (s1[i + m - 1] - s1[i - 1]));
29.     }
30.   
31.     cout << res;
32.   
33.     return 0;
34. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。