Решение задачи Разделение массива с Codeforces

Без пояснения   Просмотров: 20


У вас есть отсортированный массив a1,a2,…,an (для любого индекса i>1 выполняется условие ai≥ai−1) и число k.

Вам нужно разделить этот массив на k непустых последовательных подотрезков. Каждый элемент должен принадлежать ровно одному подотрезку.

Пусть max(i) будет равно максимуму в i-м подотрезке, а min(i) будет равно минимуму в i-м подотрезке. Тогда цена разделения будет равна ∑i=1k(max(i)−min(i)). Например, если массив a=[2,4,5,5,8,11,19] и мы разделили его на 3 подотрезка следующим образом: [2,4],[5,5],[8,11,19], тогда цена разделения будет равна (4−2)+(5−5)+(19−8)=13.

Посчитайте минимальную цену разделения массива a на k непустых последовательных подотрезков.

Код

#include<bits/stdc++.h>
using namespace std;
int q[350000],m[350000];
int main()
{
	int n,i,k,sum=0;
	cin>>n>>k;
	for(i=1;i<=n;i++)
		cin>>q[i];
	for(i=1;i<=n-1;i++)
		m[i]=q[i+1]-q[i];
	sort(m+1,m+n);
	for(i=1;i<=n-k;i++)
		sum+=m[i];
	cout<<sum<<endl;
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться