Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Info Coronavirus/Vaccinare vs Fake News

Brother Eroare scanare A9

Achizitie auto

Procedura Preschimbare nr verzi p...
 Copiii si obezitatea

Reglare greutate doza Unitra GS-431

Potrivire jante ?

instant sau dus electric?
 Microfon extern pentru ML/DSLR

Schimbare parbriz

Costuri achiziție garsoniera.

Pensii publice - Venit total asig...
 Solutie (lichid pulverizat) pentr...

Backup calling

Ce placa video recomandati si car...

Telecomanda cu touch triplu PNI S...
 

Poziție maxima .

- - - - -
  • Please log in to reply
4 replies to this topic

#1
Arrowwq

Arrowwq

    New Member

  • Grup: Candidate Members
  • Posts: 16
  • Înscris: 12.01.2022
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
sftpdt

sftpdt

    Senior Member

  • Grup: Senior Members
  • Posts: 3,320
  • Înscris: 29.08.2013

Vizualizare mesajArrowwq, pe 17 mai 2022 - 14:49, a scris:

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
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 27,492
  • Înscris: 10.08.2005

View PostArrowwq, on 17 mai 2022 - 14:49, said:

Afișează rezultatul corect , dar primesc limita de timp depășită . Unde greșesc ? Ce as putea îmbunătăți?
binary search

Edited by MarianG, 17 May 2022 - 17:05.


#4
sags

sags

    Senior Member

  • Grup: Senior Members
  • Posts: 7,068
  • Înscris: 24.04.2013
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
sags

sags

    Senior Member

  • Grup: Senior Members
  • Posts: 7,068
  • Înscris: 24.04.2013
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

Bun venit pe Forumul Softpedia!

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate