Second Opinion
Folosind serviciul second opinion ne puteți trimite RMN-uri, CT -uri, angiografii, fișiere .pdf, documente medicale. Astfel vă vom putea da o opinie neurochirurgicală, fără ca aceasta să poată înlocui un consult de specialitate. Răspunsurile vor fi date prin e-mail în cel mai scurt timp posibil (de obicei în mai putin de 24 de ore, dar nu mai mult de 48 de ore). Second opinion – Neurohope este un serviciu gratuit. www.neurohope.ro |
Poziție maxima .
Last Updated: May 22 2022 07:34, Started by
Arrowwq
, May 17 2022 14:49
·
0
#1
Posted 17 May 2022 - 14:49
Se dau doua șiruri de numere ordonate crescător,N (primul șir ) și M(al doilea șir)
Afișează, pentru fiecare dintre cele M numere citite, poziția cea mai din dreapta pe care se găsește în primul șir . Valorile vor fi afișate separate prin spații, iar numerotarea pozițiilor se va face începând cu valoarea 1. Toate elementele din al doilea șir se găsesc în primul. Restricții: 1<= N <=1.000.000 1<= M <=1.000 1<= X <=500. Exemple : 10 1 2 3 4 4 4 5 6 6 7 4 2 6 5 4 Date de ieșire: 2 9 7 6 La aceasta rezolvare primesc 80 puncte,(limita de timp depășită). #include <iostream> using namespace std; int n, m, n_elements[1000001], searching_m[1001]; int main() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> n_elements[i]; } cin >> m; for (int i = 1; i <= m; ++i) { cin >> searching_m[i]; } for (int i = 1; i <= m; i++) { for (int j = n; j >= 1; j--) { if (searching_m[i] == n_elements[j]) { cout << j << " "; break; } } } return 0; } Afișează rezultatul corect , dar primesc limita de timp depășită . Unde greșesc ? Ce as putea îmbunătăți? Edited by MarianG, 17 May 2022 - 17:02. |
#2
Posted 17 May 2022 - 16:57
Arrowwq, on 17 mai 2022 - 14:49, said:
Restricții: [..] 1<= X <=500. Deci elementele sunt din intervalul [1,500]. Te poți folosi de faptul că elementele șirului sunt ordonate crescător, și să îți construiești un vector de 501 elemente de exemplu, unde elementul de pe poziția i este ultima poziție a numărului i din șirul citit (dacă există). Exemplu concret: Ai șirul 1 2 3 3 3 4 4 5. Ești la poziția 5, ai citit valoarea 3 cu portocaliu și observi că următoarea valoare (4) este diferită, deci poziția ultimei apariții a numărului 3 este 5. |
#3
Posted 17 May 2022 - 17:04
#4
Posted 17 May 2022 - 19:58
Foloseste tehnica de comparatie si avans in cele doua siruri de la interclasare, doar ca aici nu intereseaza sa copieze valorile comasate in alta parte ci doar sa colecteze informatii despre unde da peste elemente egale/ mai mari. Asa se parcurg o singura data toate elementele, deci timp de executie liniar in numarul total de elemente ale celor 2 siruri.
|
#5
Posted 22 May 2022 - 07:34
Acum observ o chestiune care afecteaza solutia propusa de mine: in enunt zice ca sirurile (deci ambele) sunt ordonate crescator dar in exemplu cel de al doilea nu este. Bine, enuntul este oricum tamp, pentru ca la inceput N si M sunt sirurile insele dupa care se transforma brusc in numar de elemente din siruri, iar la restrictii apare un X care nu stim ce este (da’ incercam sa ghicim: valori de elemente ale sirurilor)…
Daca intervalul de valori este atat de mic, solutia propusa de @sftpdt este foarte buna: timp de executie liniar si mai ales ca nu e nevoie ca sirurile sa fie stocate in memorie (ca primul are 1 meleon de elemente). Cu o mica modificare fata de ce a scris colegul (care e chiar o simplificare), aceasta solutie nu cere ca sirurile (niciunul din ele) sa fie deja sortate. |
Anunturi
▶ 0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users