# PBinfo #1783 – FindMin – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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.

## Cod sursă C++

```cpp
#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 << "\n";
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1783)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1783/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1783/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)