[ SuPeR_MaSteR @ 23.12.2006. 15:08 ] @
Imam jedan zadatak: Potrebno je ucitati N (0 < N <= 10000) brojeva koji u zadatku predstavljaju broj "ljudi" a zatim u narednih N linija nalaze se dva broja A[j] i B[j], gde A[j] prestavlja interval u opsegu [1..1000000] kada je osoba dosla na "zurku" a B[j] interval kada je osoba otisla za zurke. Na standardni izlaz ispisati jedan broj, maksimalan broj ljudi koji je u istom intervalu (trenutku) bio na zurci. Vremensko Ogranicenje : 1 sekunda E sad, ja sam to resio tako sto sam medju ulaznim vrednostima prvo pronasao minimalni i maximalni element, i oni predstavljaju uslov izvrsavanja petlje,tj. ponavljanje petlje se izvrsava dok je max > min. A zatim deklarisao sam dva brojaca: prvi se inkrementira u slucaju da je (i >= a[j] and i <= b[j]) uslov ispunjen, to jest ako je trenutna vrednost u intervalu a[j] i b[j], a zatim se u drugom brojacu pamti najveca vrednost prvog brojaca kako bi se znao najveci broj ljudi koji je bio prisutan u istom trenutku. Evo kod: Code: #include<iostream> using namespace std; int main() { int n; cin >> n; int a[n],b[n]; int min,max; for (int i = 0; i < n; i++) { cin >> a[i] >> b[i]; if (i == 0) min = a[0],max = b[0]; else { if (min > a[i]) min = a[i]; if (max < b[i]) max = b[i]; } } int br1 = 0,br2 = 0; for (int i = min; i < max; i++,br1 = 0) { for (int j = 0; j < n; j++) if (i >= a[j] and i <= b[j]) br1++; if (br1 > br2) br2 = br1; } cout << br2; return 0; } Tacna su resenja, ali problem je sto program prelazi vremensko ogranicenje. Ima li neko ideju kako ovo da se resi na drugaciji nacin, tako da se kod optimizuje?? |