Najszybszy sposób na znalezienie minimalnego iloczynu 2 elementów tablicy zawierających ponad 200 000 elementów

Mam tablicę a[n]. Numer njest wprowadzany przez nas. Muszę znaleźć minimalny produkt a[i]i a[j]jeśli:

1) abs(i - j) > k

2) a[i] * a[j]jest zminimalizowany

Oto moje rozwiązanie (bardzo naiwne):

#include <iostream>
using namespace std;
#define ll long long
int main() {
    ll n,k; cin >> n >> k;

    ll a[n]; for(ll i=0;i<n;i++) cin >> a[i];

    ll mn; bool first = true;

    for(ll i=0;i<n;i++) {
        for(ll j=0;j<n;j++) {
            if(i!=j)
            if(abs(i-j) > k) {
                if(first) {
                    mn = a[i]*a[j];
                    first = false;
                } else if(a[i]*a[j] < mn) mn = a[i]*a[j];
            }
        }
    }
    cout << mn << endl;
}

Ale chcę wiedzieć, czy istnieje szybszy sposób na znalezienie minimalnego produktu z odległością?

Zakładając, że jest co najmniej jedna para elementów spełniających warunki i nie ma w niej mnożenia się dwóch elementów, można to zrobić w najgorszym i najlepszym przypadku w Theta(n-k)czasie i Theta(1)przestrzeni, z czymś takim:

auto back_max = a[0];
auto back_min = a[0];
auto best = a[0]*a[k+1];

for(std::size_t i=1; i<n-(k+1); ++i) {
    back_max = std::max(back_max, a[i]);
    back_min = std::min(back_min, a[i]);
    best = std::min(best, std::min(a[i+k+1]*back_max, a[i+k+1]*back_min));
}

return best;

Jest to optymalne pod względem asymptotycznej złożoności najgorszego przypadku zarówno w czasie, jak i przestrzeni, ponieważ optymalny produkt może znajdować a[0]się n-(k+1)co najmniej z dowolnym elementem w odległości k+1, więc co najmniej n-(k+1)liczby całkowite muszą być odczytane przez dowolny algorytm rozwiązujący problem.

Idea stojąca za algorytmem jest następująca:

Optymalny produkt wykorzystuje dwa elementy a, zakładając, że są to a[r]i a[s]. Bez utraty ogólności możemy założyć, że s > rponieważ produkt jest przemienny.

Z powodu ograniczenia abs(s-r) > kto implikuje s >= k+1. Teraz skażdy z indeksów może spełniać ten warunek, więc powtarzamy te wskaźniki. Taka jest iteracja ipokazanego kodu, ale jest ona przesuwana k+1dla wygody (tak naprawdę nie ma znaczenia). Dla każdej iteracji musimy znaleźć optymalny produkt o i+k+1największym indeksie i porównać go z poprzednią najlepszą oceną.

Możliwe indeksy, i+k+1z którymi można się sparować, są wszystkie mniejsze lub równe ize względu na wymaganą odległość. Musielibyśmy również powtórzyć te wszystkie, ale nie jest to konieczne, ponieważ minimum a[i+k+1]*a[j]przekroczenia justalonego ijest równe min(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j]))monotoniczności produktu (biorąc minimum w odniesieniu zarówno do minimum, jak i maksimum, z a[j]uwzględnieniem dwóch możliwych oznaki a[i+k+1]lub równoważnie dwa możliwe kierunki monotoniczności).

Ponieważ zbiór a[j]wartości, nad którymi możemy zoptymalizować jest tu po prostu {a[0], ..., a[i]}, co po prostu narośl przez jeden element ( a[i]) w każdej iteracji i, możemy po prostu śledzić max(a[j])i min(a[j])z pojedynczych zmiennych, aktualizując je, jeśli a[i]jest większy lub mniejszy niż w poprzednich wartości optymalnych. Odbywa się to back_maxi back_minna przykładzie kodu.

Pierwszy krok iteracji ( i=0) jest pomijany w pętli i zamiast tego wykonywany jako inicjalizacja zmiennych.

Nie jestem pewien co do najszybszego .

Dla prostszego problemu bez i <j - k , minimalny produkt należy do produktów par dwóch najmniejszych i największych elementów.

Tak więc (poniższe czynności są zbyt skomplikowane, patrz odpowiedź orzecha włoskiego )
(• pomiń, jeśli k ≤ n
  • zainicjuj minProdukt na [0] * a [k + 1])

• utrzymuj dwie dynamiczne struktury danych minmax do góry i dalejIplusK,
  zaczynając od {} i {a [ j ] | k ≤ j }
• dla każdego i od 0 do n - k - 1
  • dodaj [ i ] do upToI
  • usuń [ i + k ] z beyondIplusK
  • sprawdź, czy jest nowy minimalny produkt spośród
    min ( upToI ) × min ( beyondIplusK ), min ( upToI ) × max ( beyondIplusK ),
    max ( upToI ) × min ( beyondIplusK ) i max ( upToI ) × max ( beyondIplusK )

Dla „minimalnej wielkości”

Znajdź 2 elementy „najmniejszej wielkości”, a następnie (po znalezieniu dwóch zer lub przeszukaniu całej tablicy) pomnóż je.

Dla „najniższej wartości” bez abs(i - j) > kczęści

Istnieją 3 możliwości:

• dwie najwyższe (najmniejszej wielkości) liczby ujemne

• dwie najniższe (najmniejsze wielkości) liczby nieujemne

• najniższa (największa jasność) liczba ujemna i najwyższa (największa jasność) liczba nieujemna

Możesz wyszukać wszystkie 6 wartości i dowiedzieć się, które produkty są najlepsze na koniec.

Jednak; jak tylko zobaczysz zero, wiesz, że nie musisz więcej wiedzieć o pierwszych 2 możliwościach; a gdy tylko zobaczysz jedną liczbę ujemną i jedną nieujemną, wiesz, że zależy ci tylko na trzeciej możliwości.

Prowadzi to do skończonej maszyny stanów z 3 stanami - „dbaj o wszystkie 3 możliwości”, „odpowiedź wynosi zero, chyba że liczba ujemna jest widoczna” i „dbaj tylko o ostatnią możliwość”. Można to zaimplementować jako zestaw 3 pętli, gdzie 2 pętle wskakują do ( goto) środka innej pętli, gdy zmienia się stan (maszyny skończonej).

W szczególności może to wyglądać nieco niejasno (nieprzetestowane):

   // It could be any possibility

   for(ll i=0;i<n;i++) {
       if(a[i] >= 0) {
            if(a[i] < lowestNonNegative1) {
                lowestNonNegative2 = lowestNonNegative1;
                lowestNonNegative1 = a[i];
            }
            if(lowestNonNegative2 == 0) {
                goto state2;
            }
       } else {
            if(a[i] > highestNegative1) {
                highestNegative2 = highestNegative1;
                highestNegative1= a[i];
            }
            if(lowestNonNegative1 < LONG_MAX) {
                goto state3;
            }
       }
   }
   if(lowestNonNegative2 * lowestNonNegative1 < highestNegative2 * highestNegative1) {
       cout << lowestNonNegative2 * lowestNonNegative1;
   } else {
       cout << highestNegative2 * highestNegative1;
   }
   return;

   // It will be zero, or a negative and a non-negative

   for(ll i=0;i<n;i++) {
state2:
       if(a[i] < 0) {
           goto state3;
       }
   }
   cout << "0";
   return;

   // It will be a negative and a non-negative

   for(ll i=0;i<n;i++) {
state3:
       if(a[i] < lowestNegative) {
           lowestNegative = a[i];
       } else if(a[i] > highestNonNegative) {
           highestNonNegative = a[i];
       }
    }
    cout << lowestNegative * highestNonNegative;
    return;

Dla „najniższej wartości” z abs(i - j) > kczęścią

W tym przypadku nadal masz 3 możliwości; i może sprawić, że będzie działać z tym samym podejściem „3 pętle ze skończoną maszyną stanów”, ale robi się zbyt bałaganiarski / brzydki. W tym przypadku lepszym rozwiązaniem jest wstępne skanowanie tablicy w celu ustalenia, czy są jakieś zera i czy wszystkie są ujemne czy wszystkie dodatnie; aby po wstępnym skanowaniu można było wiedzieć, że odpowiedź wynosi zero, lub wybrać pętlę zaprojektowaną tylko dla konkretnej możliwości.