Skalowanie tablicy C++

Question

Witam, dałby ktoś jakąś implementację skalowania elementów tablicy? Chodzi o to, że, jeśli mam tablicę tab[] = {1, 10, 100000000000, 5, 9}, to żeby zmodyfikować ja tak, żeby wyglądała tak: {1, 4, 5, 2, 3}, czyli, żeby zależności, między nimi pozostały (np. pierwszy nadal jest mniejszy od np. drugiego elementu), ale, żeby wartości były jak najmniejsze, ale jednocześnie dodatnie.

Wiem, że trzeba jakoś użyć std::pair albo własnej struktury, ale nie wiem własnie jak. Pomozecie? Dzieki z gory

Answer 1

Sortujesz liczby w strukturze, trzymając wartość oraz idx. I teraz łatwo możesz odtworzyc wynik, bo np jeśli najmniejsza liczba (już posortowana) ma idx 5, to jeśli tablica wyn trzyma wyn, to wyn[5] = 1, i tak idziesz sobie od najmniejszych. O(N lg N), ze względu na konieczność sortowania.

Comments

udalo mi sie cos takiego zrobic na razie, ale nie rozumiem troche o co chodzi z ta tablica wyn.

#include <iostream>
#include <algorithm>

using namespace std;

struct Element
{
	int war, idx;

	bool operator < (Element &element)
    {
		if (war == element.war)
			return (idx < element.idx);
		return (war < element.war);
	}
};

Element a[100];
int n;

int main()
{
	cin >> n;

	for (int i = 1; i <= n; i++)
    {
		cin >> a[i].war;
		a[i].idx = i;
	}

	sort(a + 1, a + n + 1);
}

 

---

Tablica wyn, to to co chcesz uzyskać, zwrócić jako wynik.

---

ahahh, dobra juz kumam, bo wiesz, potrzebuje tego do zadania radiotelegraf

---

i juz zaczynam implementacje

---

no właśnie, to jest ten proces skalowania.

---

Zamiast dopisywać pole  można zastosować oddzielną tablice intów, traktowanych jako indeksy tablicy wyjściowej i posortować te inty. Coś jak klucze w bazach danych. Oryginalna tablica jest nie zmieniana. Można mieć wiele takich tablic sortujących, według różnych kryteriów.