3678. 方差

LzQuarter
#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;
}
你当前正在回复 博客/题目
存在问题!