Оптимизация алгоритма C++: найти K-комбинацию из N элементов

Question

Я довольно noobie с C++, и я пытаюсь сделать некоторые проблемы HackerRank как способ работать над этим.
Сейчас я пытаюсь решить проблему Сердитых Детей: https://www.hackerrank.com/challenges/angry-children

В принципе, он просит, чтобы создать программу, которая для заданного множества N целого, находит наималейшую возможную «нечестность» для K-длиной подмножества этого множества , Несправедливость определяется как разница между максимальным и минимальным подмножеством K-длины.

Теперь я собираюсь найти все подмножества K-длины и рассчитать их несправедливость, отслеживая наименьшую несправедливость.

Я написал программу следующие C++, который, кажется, проблема правильно:

#include <cmath> 
#include <cstdio> 
#include <iostream> 

using namespace std; 

int unfairness = -1; 
int N, K, minc, maxc, ufair; 
int *candies, *subset; 

void check() { 
    ufair = 0; 
    minc = subset[0]; 
    maxc = subset[0]; 

    for (int i = 0; i < K; i++) { 
     minc = min(minc,subset[i]); 
     maxc = max(maxc, subset[i]); 
    } 

    ufair = maxc - minc; 

    if (ufair < unfairness || unfairness == -1) { 
     unfairness = ufair; 
    } 
} 

void process(int subsetSize, int nextIndex) { 
    if (subsetSize == K) { 
     check(); 
    } else { 
     for (int j = nextIndex; j < N; j++) { 
      subset[subsetSize] = candies[j]; 
      process(subsetSize + 1, j + 1); 
     } 
    } 
} 

int main() { 
    cin >> N >> K; 
    candies = new int[N]; 
    subset = new int[K]; 

    for (int i = 0; i < N; i++) 
     cin >> candies[i]; 

    process(0, 0); 

    cout << unfairness << endl; 

    return 0; 
} 

Проблема в том, что HackerRank требует программу, чтобы придумать решение в течение 3 секунд, и что моя программа занимает больше времени, чем в найти решение для 12/16 тестовых случаев. Например, один из тестовых случаев имеет N = 50 и K = 8; программа занимает 8 секунд, чтобы найти решение на моей машине. Что я могу сделать для оптимизации моего алгоритма? Я не очень разбираюсь в C++.

Answer 1

Все, что вам нужно сделать, это сортировать все числа в порядке возрастания, а затем получить минимальную a[i + K - 1] - a[i] для всех i от 0 до N - K включительно. Это верно, потому что в оптимальном подмножестве все числа расположены последовательно в отсортированном массиве.

Answer 2

Одно из предложений, которое я бы дал, заключается в сортировке целочисленного списка перед выбором подмножеств. Это значительно сократит количество подмножеств, которые вам нужно изучить. На самом деле вам даже не нужно создавать подмножества, просто посмотрите на элементы в индексе i (начиная с 0) и i + k, а самая низкая разница для всех элементов в i и i + k [в допустимых границах] ваш ответ. Так что теперь вместо n выберите k подмножеств (факториальное время выполнения, я считаю) вам просто нужно посмотреть на ~ n подмножеств (линейное время исполнения) и сортировка (nlogn) становится вашим узким местом в производительности.