Saya memiliki sebuah array a[n]
. Nomor n
tersebut dimasukkan oleh kami. Saya perlu mencari produk minimal a[i]
dan a[j]
jika:
1) abs(i - j) > k
2) a[i] * a[j]
diminimalkan
Inilah solusi saya (sangat naif):
#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;
}
Tapi saya ingin tahu apakah ada cara yang lebih cepat untuk menemukan produk minimal dengan jarak?
c++
algorithm
optimization
minimum
Mouvre
sumber
sumber
std::vector
? @Scheff - pengurutan akan menghancurkan hubungan "jarak" yang asli.if (i!=j) if (abs(i - j) > k)
bisa dihilangkan. Hanya mulai loop batin di i + k + 1:for (ll j = i + k + 1; j < n; ++j)
. Pemeriksaan denganfirst
dapat dihilangkan juga jikamn
diinisialisasi sebelumnya misalnya denganmn = a[0] * a[k + 1];
. (Mungkin,k
harus diperiksa padan
awalnya untuk membuat bukti-peluru ini.) Tapi itu masih O (N²). Ini harus bisa dilakukan lebih cepat ...Jawaban:
Dengan asumsi setidaknya ada sepasang elemen yang memenuhi kondisi dan tidak ada perkalian dua elemen di dalamnya meluap, ini dapat dilakukan dalam
Theta(n-k)
waktu danTheta(1)
ruang terburuk-dan-kasus terbaik, dengan sesuatu seperti ini:Ini optimal dalam hal kompleksitas kasus terburuk asimptotik untuk waktu dan ruang karena produk yang optimal mungkin
a[0]
dengan salah satun-(k+1)
elemen dalam jarak setidaknyak+1
, sehingga setidaknyan-(k+1)
bilangan bulat perlu dibaca oleh algoritma yang memecahkan masalah.Gagasan di balik algoritma adalah sebagai berikut:
Produk optimal menggunakan dua elemen
a
, anggap inia[r]
dana[s]
. Tanpa kehilangans > r
sifat umum kita dapat mengasumsikan bahwa karena produk tersebut bersifat komutatif.Karena pembatasan
abs(s-r) > k
ini menyiratkan bahwas >= k+1
. Sekarangs
bisa masing-masing indeks memenuhi kondisi ini, jadi kami beralih pada indeks ini. Itu adalah iterasii
di atas dalam kode yang ditampilkan, tetapi digeser olehk+1
untuk kenyamanan (tidak terlalu penting). Untuk setiap iterasi kita perlu menemukan produk optimal yang melibatkani+k+1
sebagai indeks terbesar dan membandingkannya dengan tebakan terbaik sebelumnya.Kemungkinan indeks untuk dipasangkan
i+k+1
adalah semua indeks lebih kecil atau samai
karena persyaratan jarak. Kita perlu mengulangi semua ini juga, tetapi itu tidak perlu karena minimuma[i+k+1]*a[j]
kelebihanj
pada saati
yang sama adalahmin(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j]))
karena monotonitas produk (mengambil minimum sehubungan dengan minimum dan maksimum atasa[j]
akun untuk dua kemungkinan) tanda-tandaa[i+k+1]
atau ekuivalen dua kemungkinan arah monotonisitas.)Karena himpunan
a[j]
nilai yang kami optimalkan di sini adalah adil{a[0], ..., a[i]}
, yang hanya tumbuh dengan satu elemen (a[i]
) di setiap iterasii
, kami hanya dapat melacakmax(a[j])
danmin(a[j])
dengan variabel tunggal dengan memutakhirkannya jikaa[i]
lebih besar atau lebih kecil dari nilai optimal sebelumnya. Ini dilakukan denganback_max
danback_min
dalam contoh kode.Langkah pertama dari iterasi (
i=0
) dilewati dalam loop dan sebagai gantinya dilakukan sebagai inisialisasi variabel.sumber
a[i+k+1]
adalah minimum dan maksimum.Tidak yakin tentang yang tercepat .
Untuk masalah yang lebih sederhana tanpa i <j - k , produk minimal adalah di antara produk pasangan dari dua elemen terkecil dan terbesar.
Jadi, (yang berikut ini terlalu rumit, lihat jawaban walnut )
(• menolak jika k ≤ n
• menginisialisasi minProduk ke [0] * a [k + 1])
dimulai dengan {} dan {a [ j ] | k ≤ j }
min ( upToI ) × min (di luarIplusK ), min ( upToI ) × maks (di luarIplusK ),
maks ( upToI ) × min (di luarIplusK ) dan maks ( upToI ) × maks (di luarIplusK )
sumber
minUpto
,maxUpto
,minBeyond
,maxBeyond
(Anda dapat membuat dalam dua iterasi)? Kemudian, dalam iterasi ketiga, untuk setiap indeks, temukan perkalian min yang mungkin.Untuk "magnitudo minimum"
Temukan 2 elemen "magnitudo terkecil", lalu (setelah Anda menemukan dua nol atau mencari seluruh array), gandakanlah.
Untuk "nilai terendah" tanpa
abs(i - j) > k
bagianAda 3 kemungkinan:
dua angka negatif tertinggi (terkecil terkecil)
dua angka non-negatif terendah (terkecil terkecil)
angka negatif terendah (terbesar) dan tertinggi (terbesar terbesar) non-negatif
Anda bisa mencari semua 6 nilai dan mencari tahu produk dan mana yang terbaik pada akhirnya.
Namun; segera setelah Anda melihat nol Anda tahu Anda tidak perlu tahu lagi tentang 2 kemungkinan pertama; dan segera setelah Anda melihat satu angka negatif dan satu angka non-negatif Anda tahu bahwa Anda hanya peduli pada kemungkinan ketiga.
Ini mengarah ke mesin negara terbatas dengan 3 negara - "peduli tentang semua 3 kemungkinan", "jawabannya nol kecuali angka negatif terlihat" dan "hanya peduli tentang kemungkinan terakhir". Ini dapat diimplementasikan sebagai satu set 3 loop, di mana 2 loop melompat ke (
goto
) di tengah loop lain ketika keadaan (dari mesin keadaan terbatas) berubah.Secara khusus, ini mungkin terlihat seperti samar-samar (belum diuji):
Untuk "nilai terendah" dengan
abs(i - j) > k
bagian ituDalam hal ini Anda masih memiliki 3 kemungkinan; dan bisa membuatnya bekerja dengan pendekatan yang sama "3 loop dengan mesin negara yang terbatas" tetapi terlalu berantakan / jelek. Untuk kasus ini, alternatif yang lebih baik kemungkinan untuk melakukan pra-pemindaian array untuk menentukan apakah ada nol dan apakah semuanya negatif atau semuanya positif; sehingga setelah pra-pemindaian Anda dapat mengetahui jawabannya adalah nol atau pilih satu loop yang dirancang untuk kemungkinan tertentu saja.
sumber