Cerința

Se dă un șir P de lungime N cu elemente distincte din mulțimea {1,2..,N}. Pentru fiecare poziție i din șirul P se cere să aflați cea mai mică poziție j, astfel încât P[j] < P[i] și j < i. În caz că o astfel de poziție nu există se consideră -1 ca soluție.

Date de intrare

Fișierul de intrare findmin.in conţine pe prima linie N, reprezentând lungimea șirului iar pe a doua linie N numere naturale, reprezentând elementele șirului P.

Date de ieșire

Fișierul de ieșire findmin.out va conține pe prima linie N numere despărțite prin câte un spațiu, unde al i-lea număr reprezintă răspunsul pentru al i-lea element din șir.

Restricții și precizări

1 ≤ N ≤ 1 000 000
Șirul P este indexat de la 1.

Exemplu

findmin.in

7
5 6 7 3 1 4 2

findmin.out

-1 1 1 -1 -1 4 5

Explicație

Pentru primele 2 elemente răspunsurile sunt -1 respectiv 1. Pentru al 3-lea element răspunsul e poziția 1(se observă că și P[2] < P[3]). Pentru elementele de pe pozițiile 4 și 5 răspunsurile sunt: -1 și -1. Răspunsul pentru al 6-lea element: poziția 4 (se observa că și P[5] < P[6]). În final, răspunsul pentru ultimul elementul: poziția 5.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema FindMin:

#include <bits/stdc++.h>
 
using namespace std;
 
 
const string folderPath = "";
 
const string in_fileName = "findmin.in";
const string in_filePath = folderPath + in_fileName;
 
const string out_fileName = "findmin.out";
const string out_filePath = folderPath + out_fileName;
 
ifstream f(in_filePath);
ofstream g(out_filePath);
 
 
#define pb push_back
#define ll long long
#define mp make_pair
 
const int NMAX = 1000000;
const int nmax = 1e6 + 5;
 
int n, p[nmax], marcat[nmax], sol[nmax], pos[nmax];
 
int main() {
    f >> n;
    for (int i = 1; i <= n; ++i) {
        f >> p[i];
        pos[p[i]] = i;
    }
 
    for (int i = 1; i <= n; ++i) {
        marcat[p[i]] = 1;
        for (int j = p[i] + 1; j <= n; ++j) {
            if (marcat[j]) {
                break;
            }
            sol[ pos[j] ] = i;
            marcat[ j ] = 1;
        }
    }
 
    for (int i = 1; i <= n; ++i) {
        if (sol[i] == 0) {
            sol[i] = -1;
        }
        g << sol[i] << " ";
    }
    g << "
";
 
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1783 FindMin

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1783 FindMin de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1783 FindMin