Ваш университет вовсю готовится к новому сезону командных олимпиад. Как несложно догадаться, для этого необходимо собрать команду, которая будет представлять учебное заведение.
Всего в университете учатся n студентов, і-й из них имеет силу аi. Для участия в олимпиадах необходимо выбрать ровно k людей и расположить их в каком-то порядке. Пусть были выбраны студенты с номерами i1, i2, … , ik (именно в таком порядке).
Тогда слабость команды равна |ai2 — ai1| + |ai3, — ai2,| +… + |aik — aik-1|. Иначе говоря, слабость команды равна сумме модулей разностей сил соседних участников команды, если их расположить в выбранном порядке. Обратите внимание, что порядок студентов вы выбираете сами.
Администрация университета просит вас определить минимально возможную слабость команды.
1 Ответ
Решение можно написать таким образом:
C++:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, k;
cin >> n;
cin >> k;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
long long ans = 0, sum = 0;
for (int i = 1; i < k; i++) {
sum += a[i] — a[i — 1];
}
ans = sum;
for (int i = k; i < n; i++) {
sum = sum — (a[i — k + 1] — a[i — k]) + a[i] — a[i — 1];
ans = min(ans, sum);
}
cout << ans;
}
Python:
n = int(input())
k = int(input())
a = [0] * n
for i in range(n):
a[i] = int(input())
a.sort()
ans = 0
sum = 0
for i in range(1, k):
sum += a[i] — a[i — 1]
ans = sum
for i in range(k, n):
sum = sum — (a[i — k + 1] — a[i — k]) + a[i] — a[i — 1]
ans = min(ans, sum)
print(ans)