Решение задачи Гвоздики с Acmp

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

На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.

Код 

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int n, bb;
    cin >> n;
    vector<int> a;
    vector<int> s;
    for(int i = 0; i < n; ++i){
        cin >> bb;
        a.push_back(bb);
    }
    sort(a.begin(),a.end());
    if(n == 2){
       cout << a[1] + a[0];
       return 0;
    }
   
    s.push_back(a[1] - a[0]);
    s.push_back(a[2] - a[0]);
    for(int i = 2; i < a.size() - 1; ++i)
        s.push_back(min(s[i - 1],s[i - 2]) + abs(a[i] - a[i + 1]));
 
    cout << s[s.size() - 1];
    return 0;
}

         

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



Комментарии

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


© 2020 HSECODES bminhojkhon03@gmail.com Карта сайта