Race- utilizzo vector

Aiuto
1

ciao, ho provato ad usare i vector per risolvere l’esercizio ‘race’ ma ci sono molti errori che non riesco a risolvere…

#include <vector>
#include<algorithm>
using namespace std;

int eliminazione(int dim, int M()){
	if(dim==1){
		int w=M[0];
		return w;
	} else{
		sort(M.begin(), M.end());
		eliminazione(dim-1, M);
	}
}

int main() {
	//freopen("input.txt", "r",stdin);
	//freopen("output.txt", "w", stdout);
	int n;
	cin>>n;
	vector <int> A(n), B(n);
	int i;
	for(i=0;i<n;i++){
		cin>>A[i]>>B[i];
	}
	int eliminato, max=A(0);
	for(i=1;i<n;i++){
		if(A[i]>max){
			max=A[i];
			eliminato=i;
		}
	}
	A.erase(A.begin()+eliminato);
	B.erase(B.begin()+eliminato);
	n--;
	/*for(i=0;i<n;i++){
		cout<<A[i]<<" ";
	}
	cout<<endl;
	for(i=0;i<n;i++){
		cout<<B[i]<<" ";
	}*/
	int win=eliminazione(n, B);
	win= find(B.begin(), B.end(), win);
	cout<<win;
	return 0;
}
2

Potrei elencarti gli errori sintattici presenti nel tuo codice, ma trovo molto più istruttivo che sia tu a trovarli e correggerli.

Quindi facciamo una cosa: copia e incolla qui l’output della compilazione del sorgente, e cerchiamo di capire cosa vogliono dire gli errori e come rimediare. Una volta che il codice compila, possiamo eventualmente occuparci della correttezza dell’algoritmo.

3

Grazie, alla fine ho capito il problema ed ho sistemato. Per caso sai se con un vector di pair è possibile ordinarlo con il sort secondo il secondo elemento?

4

Sì, ci sono vari modi. Te li descrivo dal più base (ma “scorretto”) al più avanzato.

Primo modo: scambiare l’ordine degli elementi nei pair. Semplicemente, anziché salvare le coppie come (a, b), le salvi come (b, a). A questo punto chiami la funzione sort e avrai i tuoi pair ordinati in base a b. L’unico caveat è che poi devi ricordarti che l’ordine degli elementi è scambiato.

Secondo modo: passare a sort una funzione compare. sort prende come terzo argomento (opzionale) una funzione che gli dice come deve ordinare gli elementi. L’ordinamento di default è il minore stretto, ma si possono definire criteri completamente diversi. In particolare, se gli elementi sono pair, puoi dire a sort di ordinarli in base al secondo elemento. Ecco come:

// fuori dal main
bool compare(const pair<int, int>& a, const pair<int, int>& b) {
    if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}

// dentro il main o qualche altra funzione
vector<pair<int, int>> v;
// riempi v in qualche modo
sort(v.begin(), v.end(), compare);

La funzione compare prende due pair di interi (se non sai cosa vogliono dire const e la &, chiedimi pure) e ritorna true se e solo se il primo deve venire prima del secondo nell’ordinamento. In questo caso, ritorna true quando il secondo elemento del primo pair è strettamente minore di quello del secondo, e se sono uguali, quando il primo elemento è minore.

Terzo modo: come prima, ma usando una lambda. Se non sai cosa sono le lambda expression, salta pure questa parte (in pratica, una lambda è una funzione che puoi scrivere direttamente all’interno di un’altra funzione). Il codice in questo caso è più compatto, ma anche più misterioso:

sort(v.begin(), v.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
   if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
});
1 Mi Piace
5

ho capito tutto tranne ‘const’, potresti spiegarmi a cosa serve?

6

non mi è chiaro a cosa serva il ‘const’,
inoltre se non ho bisogno che avvenga l’ordinamento in base la primo elemento nel caso siano uguali rimane solo return (a.second<b.second); è corretto?

7

La funziona definita come terzo parametro della funzione sort() verrà chiamata passandogli come parametri i pair contenuti nel vettore v per indirizzo(nota l’&). Il const serve a specificare che tali valori non saranno modificati dalla funzione che confronta i 2 pair.

Non ho capito cosa intendi precisamente.

In ogni caso la logica di quella funzione è: ritorna true se se a deve venire prima di b nell’ordinamento.