题解 - 统计序列
题目形貌有一天， 小Q想起了一个统计公式， 定义一个长度为m的序列，我们可以得到V,V的盘算如下：
https://i-blog.csdnimg.cn/direct/8914a37328c64eceb5063dcf1cd0c298.png
其中：
https://i-blog.csdnimg.cn/direct/c9aec029330e4e2b94b34282ebdb73d1.png
现在给你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值是https://i-blog.csdnimg.cn/direct/e6b26892b3a64b9bb5bd1415760d2ee1.png
，乘上m2后就酿成了6。
对于20%的数据，1≤m≤n≤10。
对于50%的数据，1≤m≤n≤1000。
对于100%的数据，1≤m≤n≤100000，给定的n个数的范围是0到1e4。
分析
求V乘m^2的最小值
https://i-blog.csdnimg.cn/direct/5fff263bebbf4699b3ccff2c1aed63ac.png
化简得 m * (x1 ^ 2 + x2 ^ 2 + … xm ^ 2) - (x1+x2+…xm) ^ 2
贪婪，从小到大排序，然后依次算出连续得m个数，取最小值即可
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100000 + 10;
LL n,m;
LL a,s1,s2;
LL res = 1e18 + 10;
int main(){
ios::sync_with_stdio;
cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++) cin >> a;
sort(a + 1,a + 1 + n);
for(int i = 1;i <= n;i++){
s1 = s1 + a;
s2 = s2 + a * a;
}
for(int i = 1;i <= n - m + 1;i++){
res = min(res,m * (s2 - s2) - (s1 - s1) * (s1 - s1));
}
cout << res;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]