Sto cercando di risolvere il problema persian party e credo di aver trovato una soluzione efficace. Ho sottoposto questa soluzione e in ogni test case mi dice che impiega troppo tempo. Ciò mi sembra strano. In parte è vero che per ordinare l’array uso un selection sort che impiega $O(N^2), però, per almeno i primi test case non dovrebbe dare problemi. Qualcuno mi può dare una mano?
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void pasqSort(vector<long> &arr, long l) {
for (int i = 0; i < l; i++){
int minIndex = i;
for (int j = i; j< l; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int t = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = t;
}
}
int main(){
long n;
cin >> n;
vector <long> A(n);
vector <long> D(n);
for(long i=0; i<n; i++){
cin >> A[i];
cin >> D[i];
}
cout << "HELLO";
pasqSort(A, A.size());
pasqSort(D, D.size());
int a = 0;
int d = 0;
int guests = 0;
int handshakes = 0;
while (a < n || d < n) {
while(A[a] < D[d] && a < n) {
handshakes += guests;
guests++;
a++;
}
while(D[d] < A[a] && d < n) {
guests--;
handshakes += guests;
d++;
}
}
cout<<handshakes;
return 0;
}
Personalmente non ho risolto il problema, quindi probabilmente chi l’ha risolto può darti consigli migliori. Comunque, per il momento, una semplice miglioria che puoi attuare è usare un algoritmo di ordinamento più efficace( O(NlogN)), come la funzione predefinita sort(arr.begin(), arr.end()).
Perchè stampi HELLO?
Il numero di strette di mano potrebbe non stare in un int.
Direi inoltre che guests parte da 1 (c’è un proverbio che dice che è sbagliato fare i conti senza l’oste!)
Per gli interi a 64 bit long long non solo long.
Il programma che sottometti deve leggere da file e scrivere su file.
Grazie mille per l’aiuto. Non riesco però a capire come distinguere le tipologie di esercizio. Infatti dalla traccia e anche dal file esempio che ho scaricato si intuiva che bisognasse leggere da input e poi stampare i risultati. Ora però mi stai dicendo che devo leggere e scrivere da file. Come si fa a capire quando fare cosa?
(Quell’HELLO era solo per il debugging. Nel codice che ho sottoposto non c’era.)
// uncomment the following lines if you want to read/write from files
// freopen(“input.txt”, “r”, stdin);
// freopen(“output.txt”, “w”, stdout);
Nella stragrande maggioranza dei casi, e salvo diverso avviso, si leggono i dati dal file “input.txt” e si scrivono i risultati sul file “output .txt”.
(diversamente come fa il server a valutare il tuo programma, non ha uno schiavetto che inserisce fino a 2000000 interi a mano).
Non si usano i file solo quando l’I/O non è gestito da quella parte di codice che dobbiamo sviluppare noi.
Mi continua a dare execution timed out. Non so assolutamente cosa fare. Non capisco quale sia il problema. Mi potresti dare un aiutino?
#include <assert.h>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// constraints
#define MAXN 200000
int main() {
// uncomment the following lines if you want to read/write from files
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int N;
vector <long> A;
vector <long> D;
assert(1 == scanf("%d", &N));
for (int i = 0; i < N; i++) {
long int a,b;
assert(2 == scanf("%ld%ld", &a, &b));
A.push_back(a);
D.push_back(b);
}
sort(A.begin(), A.end());
sort(D.begin(), D.end());
int a = 0;
int d = 0;
int guests = 1;
long long int handshakes = 0;
while (a < N || d < N) {
while(A[a] < D[d] && a < N) {
handshakes += guests;
guests++;
a++;
}
while(D[d] < A[a] && d < N) {
guests--;
handshakes += guests;
d++;
}
}
printf("%lld\n", handshakes); // change 42 with actual answer
return 0;
}
Non vedo chiaro cosa succede con quei due cicli while dentro il while principale:
mi spiego:
ad un certo punto gli arrivi saranno stati tutti elaborati ( e quindi a vale N) ma non tutti sono ancora usciti e quindi d<N.
Nel primo dei due while non si entra più e va bene, si dovrebbe stare nel secondo while per elaborare le ultime uscite solo che mi sembra che la condizione di questo while non vada:
while(D[d] < A[a] && d < N)
con a che vale N si fa il test sull’elemento A[N] che è fuori range.
Inoltre, sempre per lo stesso motivo:
non va bene bisogna anteporre il secondo controllo al primo.
Ovviamente vale altrettanto per l’altro while.
Apportate le modifiche ai due cicli il tuo programma fa 100/100 in meno di 0,2s.