3678. 方差

#include <bits/stdc++.h>

using namespace std;

using ull = unsigned long long;

int main() {
    ull n, m;
    cin >> n >> m;
    vector<ull> v(n);
    for (ull i = 0; i < n; ++i) cin >> v[i];
    sort(v.begin(), v.end());

    ull x = inner_product(v.begin(), v.begin() + m, v.begin(), 0ull);
    ull s = accumulate(v.begin(), v.begin() + m, 0ull);

    ull res = m * x - s * s;

    if (m != n) {
        for (ull i = 1; i + m - 1 < n; ++i) {
            x = x - v[i - 1] * v[i - 1] + v[i + m - 1] * v[i + m - 1];
            s = s - v[i - 1] + v[i + m - 1];
            res = min(res, m * x - s * s);
        }
    }

    cout << res << endl;
}

#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
int main(){
    std::ios::sync_with_stdio(false);
    ll arr[1000002];
    ll marr[1000002];
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    sort(arr, arr + n);
    for(int i = 0; i < n; i++){
        marr[i] = m * arr[i] * arr[i];
    }
    ll tempsum = 0;
    ll tempsum2 = 0;
    for(int i = 0; i < m - 1; i++){
        tempsum += marr[i];
        tempsum2 += arr[i];
    }
    int first = 0;
    int last = m - 1;
    ll minval = 1000000000000000000;
    while(last < n){

        tempsum += marr[last];
        tempsum2 += arr[last];

        ll val = 0;
        val = tempsum - tempsum2 * tempsum2;
        minval = val < minval ? val : minval;
        // cout << minval << endl;
        tempsum -= marr[first];
        tempsum2 -= arr[first];
        // while(arr[first] == arr[first+1] && arr[last] == arr[last + 1] && last < n){first++;last++;}
        // 本意是加快计算速度，可是总是会错
        last++;
        first++;
    }
    cout << minval << endl;
    return 0;
}