Rezolvare completă PbInfo #3281 sminus

Fie un șir a1, a2, …, aN de numere întregi. În acest șir se alege o pereche de indici (x, y), 1 ≤ x ≤ y ≤ N și se inversează semnul tuturor componentelor secvenței ax, ax+1, …, ay. De exemplu, pentru șirul 3, -5, 4, -1, 6, -8, -5, dacă se alege perechea (3, 5), atunci șirul va deveni 3, -5, -4, 1, -6, -8, -5.

Cerința

Să se determine o pereche de indici x y astfel încât după inversarea semnului componentelor secvenței ax, ax+1, …, ay suma elementelor din vector să fie minimă.

Date de intrare

Fișierul de intrare sminus.in conține pe prima linie numărul N. Pe a doua linie, separate prin câte un spațiu, se găsesc numerele întregi a1, a2, …, aN.

Date de ieșire

Fișierul de ieșire sminus.out va conține două linii. Pe prima linie se vor găsi două numere naturale x și y separate printr-un spațiu reprezentând perechea de indici. Pe linia a doua se va găsi un singur număr natural reprezentând suma minimă obținută prin inversarea semnului componentelor din secvența ax, ax+1, …, ay.

Restricții și precizări

  • 2 ≤ N ≤ 100.000
  • -1000 ≤ ai ≤ 1000 pentru orice i = 1..N
  • Secvența ax, ax+1, …, ay trebuie să conțină cel puțin un element.
  • Dacă există mai multe soluții pentru perechea (x, y), atunci se va alegea aceea care are indicele x minim, iar dacă sunt mai multe secvențe posibile care încep la poziția x, se va alege aceea care are valoarea y maximă.
  • Pentru teste valorând 50 de puncte, N ≤ 2000.

Exemplul 1:

sminus.in

7
3 -5 4 -1 6 -8 -5

sminus.out

3 5
-24

Explicație

Inversând semnul elementelor din secvența care începe la poziția 3 și se termină la poziția 5 se obține secvența
3, -5, -4, 1, -6, -8, -5 care are suma elementelor egală cu -24.

Exemplul 2:

sminus.in

6
2 -1 2 -2 2 -6

sminus.out

1 5
-9

Explicație

Inversând semnul elementelor din secvența care începe la poziția 1 și se termină la poziția 5 se obține secvența
-2, 1, -2, 2, -2, -6 care are suma elementelor egală cu -9. Aceeași sumă minimă se putea obține și pentru perechea de indici (1, 3), dar indicele y este mai mic.

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 sminus:

#include<bits/stdc++.h>
using namespace std;

int s[100003];
int main()
{
    int n, lo, i, st, dr, bst = -1000000000;
    ifstream fin("sminus.in");
    ofstream fout("sminus.out");
    fin >> n;
    lo=0;
    for(i = 1; i <= n; i++)
    {
        fin >> s[i];
        s[i] += s[i - 1];
        if(s[i] - s[lo] > bst)
        {
            st = lo;
            dr = i;
            bst = s[dr] - s[st];
        }
        else if (s[i] - s[lo] == bst)
        {
            if(lo <= st)
            {
                st = lo;
                dr = i;
            }
        }
        if(s[i] < s[lo]) lo = i;
    }
    fout << (st + 1) << " " << dr << "\n" << (s[n] - 2 * bst) << "\n";
    fin.close();
    fout.close();
    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 #3281 sminus

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3281 sminus 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!