• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

k-ta max wart. dynamicznego ciągu 1...n

VPS Starter Arubacloud
0 głosów
136 wizyt
pytanie zadane 1 marca 2023 w C i C++ przez polandonion Mądrala (6,970 p.)
Witam, jest jakiś algorytm wyznaczania k-tego najwiekszego elementu dynamicznego ciagu 1...n?

Chodzi o to, ze na poczatku mam ciag 1...n bez powtorzen i musze znalezc k-ta max wart. i ja usunac. potem znowu i znowu itd. O(n^2) odpada. Celuje w jakies O(n log n).
komentarz 1 marca 2023 przez tangarr Mędrzec (154,780 p.)
Czy kolejność w ciągu ma znaczenie?
komentarz 1 marca 2023 przez polandonion Mądrala (6,970 p.)
edycja 1 marca 2023 przez polandonion
ciag jest posortowany

2 odpowiedzi

+2 głosów
odpowiedź 1 marca 2023 przez Whistleroosh Maniak (56,900 p.)
wybrane 1 marca 2023 przez polandonion
 
Najlepsza

Zakładam, ze k może się zmieniać. Wtedy można to zrobić drzewem przedziałowym (w tym przypadku drzewem licznikowym). Dla każdego wierzchołka musisz wiedzieć ile wartości jest w jego poddrzewie. Wyszukiwanie działa podobnie jak quick search. Jak szukasz k-tego elementu to z danego wierzchołka możesz albo pójśc do lewego poddrzewa (gdy k <= liczba wierzchołków w lewym poddrzewie) albo prawego (wtedy k -= liczba wierzchołków w lewym poddrzewie).

Odpowiadanie na jedno zapytanie ma złożonosć O(logn), tak samo usuwanie/dodawanie wartości do drzewa.

Inne rozwiązania tego problemu: https://forum.pasja-informatyki.pl/581253/implementacja-seta-z-idxami-drzewa-licznikowego

komentarz 1 marca 2023 przez polandonion Mądrala (6,970 p.)
edycja 1 marca 2023 przez polandonion

Jeśli miałbym doprecyzować, to chodzi mi o zadanie z OI "Kodowanie Permutacji". Zrobiłem na początku taiego mega chamskiego bruta O(n^2), który dawał ledwo 30%, a potem spróbowałem zwykłego sposobu O(n) (a przynajmniej tak mi sie wydaje, ze to jest O(n)), i teraz daje mi o wiele wiecej, ale wciaz nie 100%. Wiesz co moze byc za wolne?

#include <iostream>
#include <vector>

using namespace std;

int n, zak[100001], odk[100001];
vector <int> vec;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> zak[i];
        
        if (zak[i] >= i) {
            cout << "NIE";
            return 0;
        }
    }

    for (int i = n; i >= 1; i --)
        vec.push_back(i);

    for (int i = n; i >= 1; i --) {
        odk[i] = vec[zak[i]];
        vec.erase(vec.begin() + zak[i]);
    }

    for (int i = 1; i <= n; i ++)
        cout << odk[i] << '\n';
}

PS. strzelam, ze pewnie vector::erase() psuje zlozonosc ale nw jak przyspieszyc. moze calosc przeniesc na seta i tam wyszukiwanie juz na pewno dziala w logu?

1
komentarz 1 marca 2023 przez Whistleroosh Maniak (56,900 p.)
To wciąż jest O(n^2) bo erase działa liniowo. Set nie pozwala znaleźć k-tego elementu w czasie O(logn). Trzeba zaimplementować własną strukturę, która wspiera znajdowanie k-tego elementu
komentarz 1 marca 2023 przez polandonion Mądrala (6,970 p.)

dzieki za pomoc :D, cos takiego wyklepalem i daje mi setke:

#include <iostream>
#include <algorithm>
#define N 100000

using namespace std;

int n, zak[N + 1], odk[N + 1];
int tree[3 * N], q;

void build_tree() {
	for (int i = q + 1; i <= q + n; i ++)
		tree[i] ++;

	for (int i = q; i >= 1; i --)
		tree[i] = tree[i * 2] + tree[i * 2 + 1];
}

void upd(int v) {
	while (v >= 1) {
		tree[v] --;
		v >>= 1;
	}
}

int kthElem(int k) {
	int v = 1;
	while (v <= q) {
		if (tree[v * 2 + 1] < k) {
			k -= tree[v * 2 + 1];
			v <<= 1;
		}
		else
			v = (v << 1) + 1;
	}

	upd(v);
	return v - q;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> zak[i];

		if (zak[i] >= i) {
			cout << "NIE";
			return 0;
		}
	}

	q = 1;
	while (q < n)
		q <<= 1;
	q --;

	build_tree();

	for (int i = n; i >= 1; i --)
		odk[i] = kthElem(zak[i] + 1);

	for (int i = 1; i <= n; i ++)
		cout << odk[i] << '\n';
}

 

0 głosów
odpowiedź 1 marca 2023 przez mokrowski Mędrzec (155,460 p.)
https://en.cppreference.com/w/cpp/algorithm/nth_element

Implementacje masz w linkach na stronie.

Podobne pytania

0 głosów
1 odpowiedź 135 wizyt
pytanie zadane 8 lutego 2021 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)
0 głosów
1 odpowiedź 148 wizyt
pytanie zadane 15 maja 2017 w C i C++ przez kacper1445 Gaduła (4,880 p.)
0 głosów
1 odpowiedź 1,953 wizyt

92,452 zapytań

141,262 odpowiedzi

319,079 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...