Решение задачи Лунный новый год и разделение чисел с Codeforces

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


Приближается лунный новый год, а Боб все еще мучается со своей домашней работой — задачей о разделении чисел.

Даны n положительных целых чисел a1,a2,…,an, где n всегда четно. Боб должен разделить эти числа на группы, причем каждая группа должна содержать хотя бы 2 числа. Предположим, что числа разделены на m групп, и сумма чисел в j-й группе равна sj. Цель Боба — минимизировать сумму квадратов sj, то есть
∑j=1ms2j.
Боб никак не может решить эту задачу. Можете ему помочь?

Код

#include<bits/stdc++.h>
using namespace std;
long long a[1000000];
int main()
{
    long long n,s=0;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<n/2;i++) s+=(a[i]+a[n-i-1])*(a[i]+a[n-i-1]);
    cout<<s;
}

         

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



Комментарии

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