Informatică, întrebare adresată de stassahul, 9 ani în urmă

Ceva idei la aceasta problema? (#1468)

Cerința
Se dă un şir format din n numere naturale. Un termen din şir se numeşte minim relativ dacă este mai mic sau egal decât toţi termenii din şir situaţi înaintea lui. Să se determine numărul elementelor din şir care sunt minime relative, precum şi suma maximă a elementelor dintr-o secvenţă cuprinsă între două minime relative consecutive, inclusiv acestea.

Date de intrare
Fișierul de intrare relativ.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire
Fișierul de ieșire relativ.out va conține pe prima linie numărul k, reprezentând numărul termenilor din şir care sunt minime relative, iar pe a doua linie maximul sumei elementelor dintr-o secvenţă cuprinsă între două minime relative consecutive din şir, inclusiv acestea.

Restricții și precizări
1)1 ≤ n ≤ 1.000.000
2)numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
3)o secvenţă cuprinsă între doi termeni din şir conţine 4)toţi termenii din şir situaţi între aceştia, inclusiv cei doi termeni daţi.
5)primul termen din şir este considerat minim relativ
6)şirul conţine cel puţin doi termeni care sunt minime relative
7)două minime relative sunt consecutive în şir dacă între ele nu mai este alt minim relativ
8)prima cerinţă valorează 40% din punctaj, iar a doua 60% ( în fişierul relativ.out trebuie afişate două numere pentru a primi punctaje parţiale)

Exemplu
relativ.in

9
3 5 9 2 7 11 3 4 2
relativ.out

3
29

Explicație
În şirul dat sunt trei minime relative, 3, 2 şi 2 situate pe poziţiile 1, 4, respectiv 9 în şir. Secvenţele din şir situate între două minime relative consecutive sunt 3, 5, 9, 2, respectiv 2, 7, 11, 3, 4, 2, suma elementelor acestora fiind 19, respectiv 29. Suma maximă este 29.

P.s. Va rog s-a controlati programul pe pbinfo ca sa va dea 100 puncte inainte de al pune pe brainly!


stassahul: Inca o remarca, programul poate fi nu chiar rapid, maxim 0.3 secunde!

Răspunsuri la întrebare

Răspuns de artur99
16
#include <iostream>
#include <fstream>
using namespace std;

int main(){
    ifstream in("relativ.in");
    ofstream out("relativ.out");

    long long int i, n, t;
    long long int min_count = 1, min_glob;
    long long int s, summax;

    in>>n;

    in>>t;
    s = summax = min_glob = t;

    for(i=1;i<n;i++){
        in>>t;
        s+=t;
        if(t <= min_glob){
            // am gasit un min.rel. nou
            min_glob = t;
            min_count++;
            if(s > summax){
                summax = s;
            }
            s = t;
        }
    }
    out<<min_count<<'\n'<<summax;

    return 0;
}




Sper că înțelegi :D Dacă nu, întreabă :))

stassahul: Mersi
artur99: Npc :D
Alte întrebări interesante