Минимальная разница между суммой двух чисел в массиве

Я пытаюсь решить эту проблему :

  

Профессор физики давал проекты ученикам своего класса. Студенты должны сформировать команду из двух человек для выполнения проекта. Профессор оставил студентов решать команды. Количество учеников в классе будет четным.

     

Каждый студент имеет уровень знаний. Он говорит, сколько знаний имеет каждый студент. Уровень знаний команды - это сумма уровней знаний обоих студентов.

     

Учащиеся решают сформировать группы таким образом, чтобы разница между командой с самыми высокими знаниями и командой с самыми низкими знаниями была минимальной.

     

Ввод

     

Первая строка ввода будет содержать количество тестов t; В следующих t строках первое число равно n числу учеников в классе, за которым следуют n целых чисел, обозначающих уровни знаний n учеников

     

Выход

     

Вывод должен состоять из одной строки, содержащей наименьшую возможную разницу между командой с самыми высокими знаниями и командой с самыми низкими знаниями.

Решение сводится к вычислению минимальной разницы между суммой двух чисел в несортированном массиве. Пока что я пробовал:

  1. Сортировать массив.
  2. Добавьте элементы в положениях i и n-i-1 и возьмите их абсолютную разницу с суммой элементов в положениях i + 1 и n-i.
  3. Сохраните различия в очереди приоритетов.
  4. Получите ответ в верхней части очереди с приоритетами.

И вот код, который я пробовал:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);

    int T=0,num=0;
    cin >> T;

    while(T--){
        cin >> num;
        int *a = new int[num];
        for(int i = 0; i < num; i++){
            cin >> a[i];
        }
        sort(a,a+num);
        priority_queue<int> pq;
        for(int i = 0; i < num-2; i++){
            int j = i+1;
            pq.push(abs(a[i]+a[num-1-i]-a[j]-a[num-j-1]));
        }
        cout << pq.top()<< endl;
    }
    return 0;
}

Это решение превышает ограничение по времени, и моя интуиция может дать сбой в некоторых случаях. Описание и теги подсказывают решение для динамического программирования, но почему-то я не могу вывести оптимальную подструктуру. Кто-нибудь может помочь?

7 голосов | спросил sky_coder123 12 J0000006Europe/Moscow 2015, 13:30:30

0 ответов


Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132