Question

Большая политика В некотором королевстве есть N провинций. Король пожелал объединить их все под своей самодержавной властью. Естественно, чтобы никто не догадался об этих планах, он будет это делать поэтапно, а именно: раз в год он будет объединять какие-то две провинции в одну. Чтобы жителям обеих провинций не было обидно, новому территориальному образованию будет присвоено новое название, которое будет отличаться от обоих старых названий. Естественно, это потребует выпуска новых паспортов для жителей обеих провинций. Очевидно, что если в первой провинции pi жителей, а во второй — pj жителей, то для них надо выпустить pi+pj новых паспортов. На следующий год король объединяет ещё какие-то две провинции. И так далее до тех пор, пока вся территория королевства не будет объединена в одну большую "провинцию". Определите, какое наименьшее количество новых паспортов придётся выпустить, если король будет объединять провинции оптимально с этой точки зрения. Входные данные В первой строке вводится число N (натуральное, не превышает 105) — количество провинций. Затем вводятся N чисел — количество жителей каждой провинции (натуральное, не превосходит 109). Гарантируется, что изначально в королевстве хотя бы две провинции. Выходные данные Выведите единственное число — количество новых паспортов, которые придётся выпустить. Примеры Ввод 2 2 6 Вывод 8 Ввод 3 6 2 4 Вывод 18 Решать на C++!

Answer 1

Ответ:

#include <iostream>

#include <set>

 

typedef long long ll;

 

int main()

{

   std::multiset<ll> st;

 

   {

       int n;

       ll population;

       std::cin >> n;

       for(int i = 0; i < n; ++i)

       {

           std::cin >> population;

           st.insert(population);

       }

   }

 

   ll result = 0;

   while(st.size() > 1)

   {

       ll a = *st.begin();

       ll b = *(++st.begin());

       st.erase(st.begin());

       st.erase(st.begin());

 

       a += b;

       result += a;

       st.insert(a);

   }

 

   std::cout << result;

 

   return 0;

}

Объяснение:

Решил не я!

Answer 2

Данная задача относится к теме комбинаторики и оптимизации. Оптимальное объединение провинций означает минимизацию количества новых паспортов, которые придется выпустить.

Для решения этой задачи можно использовать следующий подход на C++:

#include 
#include 
#include

using namespace std;

int main() {
    int N;
    cin >> N;
    vector population(N);
    for (int i = 0; i < N; ++i) {
        cin >> population[i];
    }

long long total_passports = 0;

// Объединяем провинции по минимальному принципу
    while (population.size() > 1) {
        auto min1 = min_element(population.begin(), population.end());
        int min1_val = *min1;
        population.erase(min1);

auto min2 = min_element(population.begin(), population.end());
        int min2_val = *min2;
        population.erase(min2);

total_passports += static_cast(min1_val) * min2_val;
        population.push_back(min1_val + min2_val);
    }

cout << total_passports << endl;

return 0;
}

Этот код считывает входные данные, находит минимальные значения, объединяет их и увеличивает общее количество паспортов на произведение чисел. Повторяя этот процесс до тех пор, пока вектор не будет содержать только один элемент, программа выводит общее количество паспортов, которые необходимо выпустить.

Обратите внимание, что этот код предполагает, что данные вводятся корректно, и не включает обработку исключений или ошибок. В реальных приложениях также может потребоваться дополнительная проверка на корректность входных данных.