Массив данных - N чисел. Найти в нем такую последовательность K чисел, чтобы сумма разниц каждых двух чисел в этой последовательности, деленная на количество этих этих пар чисел, была минимальной.
Решение на с++. Не могу составить полную картину/сложить воедино то, что он делает.
#include <bits/stdc++.h>
using namespace std;
#define lli long long
#define MAX 1000006
lli A[MAX],C[MAX];
int main()
{
int l = 1, r = 2, st,en,n;
lli sum,ans;
cin >> n >> k;
for ( int i = 1; i <= n; i++ ) cin >> A[i];
sort(A+1, A+n+1);
cum[0] = 0;
for ( int i = 1; i <= n; i++ ) cum[i] = cum[i-1] + A[i];
while ( r <= k ) {
sum += (A[r]*(r-l) - (cum[r-1] - cum[l-1]));
r++;
}
st = 1, en = k, ans = sum;
while ( r <= n ) {
sum -= (cum[r-1] - cum[l] - A[l]*(r-l-1));
l++;
sum += (A[r]*(r-l) - (cum[r-1] - cum[l-1]));
if ( ans > sum ) {
ans = sum;
st = l;
en = r;
}
r++;
}
return 0;
}
1) Объявляет список C и не использует. Он для чего?
2) cum - некая последовательность чисел, в которой каждое последующее число - это сумма всех предыдущих + текущее значение, взятое из отсортированного списка A с индексом i. Дальше не ясно.
В цикле while каждый раз увеличивается увеличивается список sum на элемент, получаемый путем умножения элемента из А с индексом r на некую разницу индексов и вычитания элементов последовательности cum с прочими индексами. Как это все сопоставляется друг с другом? Общая цель понятна, а по отдельности нет.
3) как результат выводитсся? Где cout или прочее прохожее на stdout
