Mam tablicę a[n]
. Numer n
jest 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ą?
c++
algorithm
optimization
minimum
Mouvre
źródło
źródło
std::vector
? @Scheff - sortowanie zniszczyłoby pierwotne relacje „odległości”.if (i!=j) if (abs(i - j) > k)
można wyeliminować. Wystarczy uruchomić wewnętrzną pętlę w I + k + 1:for (ll j = i + k + 1; j < n; ++j)
. Sprawdzanie za pomocąfirst
można również wyeliminować, jeślimn
zostanie zainicjowane przed npmn = a[0] * a[k + 1];
. Za pomocą . (Być możek
należy to sprawdzić nan
początku, aby uczynić to kuloodpornym.) Ale wciąż jest to O (N²). To musi być wykonalne szybciej ...Odpowiedzi:
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 iTheta(1)
przestrzeni, z czymś takim: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ścik+1
, więc co najmniejn-(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ą toa[r]
ia[s]
. Bez utraty ogólności możemy założyć, żes > r
ponieważ produkt jest przemienny.Z powodu ograniczenia
abs(s-r) > k
to implikujes >= k+1
. Terazs
każdy z indeksów może spełniać ten warunek, więc powtarzamy te wskaźniki. Taka jest iteracjai
pokazanego kodu, ale jest ona przesuwanak+1
dla wygody (tak naprawdę nie ma znaczenia). Dla każdej iteracji musimy znaleźć optymalny produkt oi+k+1
największym indeksie i porównać go z poprzednią najlepszą oceną.Możliwe indeksy,
i+k+1
z którymi można się sparować, są wszystkie mniejsze lub równei
ze względu na wymaganą odległość. Musielibyśmy również powtórzyć te wszystkie, ale nie jest to konieczne, ponieważ minimuma[i+k+1]*a[j]
przekroczeniaj
ustalonegoi
jest równemin(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, za[j]
uwzględnieniem dwóch możliwych oznakia[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 iteracjii
, możemy po prostu śledzićmax(a[j])
imin(a[j])
z pojedynczych zmiennych, aktualizując je, jeślia[i]
jest większy lub mniejszy niż w poprzednich wartości optymalnych. Odbywa się toback_max
iback_min
na przykładzie kodu.Pierwszy krok iteracji (
i=0
) jest pomijany w pętli i zamiast tego wykonywany jako inicjalizacja zmiennych.źródło
a[i+k+1]
są minimum i maksimum.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])
zaczynając od {} i {a [ j ] | k ≤ j }
min ( upToI ) × min ( beyondIplusK ), min ( upToI ) × max ( beyondIplusK ),
max ( upToI ) × min ( beyondIplusK ) i max ( upToI ) × max ( beyondIplusK )
źródło
minUpto
,maxUpto
,minBeyond
,maxBeyond
(można tworzyć w dwóch iteracjach)? Następnie, w trzeciej iteracji, dla każdego indeksu znajdź minimalne możliwe mnożenie.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) > k
częściIstnieją 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):
Dla „najniższej wartości” z
abs(i - j) > k
częś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.
źródło