Puoi leggere e provare a risolvere questo problema visitando questo indirizzo: territoriali.olinfo.it
In questo problema viene richiesto di riarrangiare i tutor in modo che ognuno abbia sotto la sua supervisione solo persone con competenza inferiore a lui. Inoltre c'è il vincolo che un tutor una volta promosso non può più essere declassato.
Innanzitutto possiamo notare che esiste un ordine di arrangiamento che rispetta la seconda condizione, e consiste nell'ordinamento decrescente secondo competenza dei tutor. Questo infatti garantisce che una volta finito di promuovere un tutor non verranno mai più promossi tutor di competenza superiore alla sua, quindi lui non verrà mai declassato.
Adesso si tratta solo di fare una simulazione, guardando ogni tutor in ordine e confrontandolo con il suo diretto superiore, scambiandoli se il primo ha un valore di competenza maggiore del secondo e ripetendo il procedimento se necessario.
C'è un problema che però sorge dopo il primo scambio, ovvero che le posizioni dei tutor non sono più le stesse e perciò ricordarsi le posizioni iniziali dei tutor non basta 🤔. Un modo per ovviare a questo problema é tenere una mappa che associa un valore di competenza (che da testo sono tutti distinti) con la posizione del tutor corrispondente. Questa all'inizio avrà le associazioni competenza/tutor dell'input per poi essere aggiornata ad ogni scambio, permettendo così di conoscere in ogni momento la posizione di un tutor in base alla sua competenza 😉
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int gerarchie(vector<int> up, vector<int> values) {
int N = up.size();
vector<int> value_to_node(N);
for (int i = 0; i < N; ++i) {
value_to_node[values[i]] = i;
}
vector<int> values_order(values.begin(), values.end());
sort(values_order.begin(), values_order.end(), greater<int>());
int count = 0;
for (int v : values_order) {
int i = value_to_node[v];
while (up[i] != -1 && values[up[i]] < values[i]) {
int u = up[i];
int vu = values[u];
// scambio u con i
value_to_node[vu] = i;
value_to_node[v] = u;
values[i] = vu;
values[u] = v;
i = u;
count++;
}
}
return count;
}
int main() {
int T;
cin >> T;
for (int t = 1; t <= T; ++t) {
int N;
cin >> N;
vector<int> parents(N), values(N);
for (int i = 0; i < N; ++i) {
cin >> parents[i] >> values[i];
}
cout << "Case #" << t << ": " << gerarchie(parents, values) << endl;
}
}