看没人贴题解我来贴一个:
此题的解法是贪心+前缀和+固定窗口思想.
因为要求是连续的数字两两数字之间的方差和最小,所以我们应该想到排序后有序的连续的数字两两之间的方差之和一定是最优解,(因为有序所以相隔两个的数字差值最小).
随后利用前缀和将所有的差值进行相加,再利用固定窗口思想,对前缀和数组进行操作,就可以解出来这道题目了.
以下是AC代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, m;
cin >> n >> m;
vector<int> vec(n);
for (int i = 0; i < n; i++)
{
cin >> vec[i];
}
sort(vec.begin(), vec.end());//排序去贪心每个差值最小
vector<int> a(n - 1);//求每两个数的平方差
for (int i = 0; i < n - 1; i++)
{
a[i] = (vec[i + 1] * vec[i + 1]) - (vec[i] * vec[i]);
}
vector<ll> b(n);//前缀和数组
for (int i = 0; i < n - 1; i++)
{
b[i + 1] = a[i] + b[i];
}
// for (auto i : b) {
// cout << i << endl;
// }
ll ans = LLONG_MAX;
for (int i = m - 1; i < n; i++) //注意你每选两个数是有一个差值,所有我们需要选m-1个数字。
{
ll val;
//利用固定窗口思想,去计算我们这m个长度的最小值
val = b[i] - b[i - m + 1];
ans = min(ans, val);
}
cout << ans << endl;
return 0;
}