Question

Cerinţa
De-a lungul principalei străzi din orașul nostru există n plopi, pentru fiecare cunoscându-se înălțimea. Primarul orașului dorește ca plopii să aibă înălțimile în ordine descrescătoare. Pentru aceasta, este posibilă tăierea dintr-un plop a unei bucăți – este o tehnică ecologică, nevătămătoare, în urma căreia plopul nu are de suferit. Plopii nu pot fi înălțați în niciun fel.

Determinați numărul minim de plopi din care se va tăia și lungimea totală minimă a bucăților tăiate.

Date de intrare
Fișierul de intrare plopi2.in conține pe prima linie numărul de plopi n. Urmează n numere naturale nenule, separate prin spaţii, care pot fi dispuse pe mai multe linii, reprezentând înălțimile plopilor.

Date de ieşire
Fișierul de ieșire plopi2.out va conține pe prima linie numerele C T, separate prin exact un spațiu, reprezentând numărul minim de plopi din care se va tăia și lungimea totală minimă a bucăților tăiate.

Restricţii şi precizări
2 ≤ n ≤ 100
înălțimile plopilor vor fi mai mici decât 10000

Answer 1

#include <iostream>

#include <fstream>

using namespace std;

int main()

{

   ifstream fin("plopi2.in");

   ofstream fout("plopi2.out");

   int i, n, taiati=0, mintaiat=0, prec, urm;

   fin >> n;

   fin >> prec;

   for (i=2; i<=n; ++i)

   {

       fin >> urm;

       if (urm>prec)       // pt strict descrescator  conditia este  (urm>=prec)

       {

           ++taiati;

           mintaiat=mintaiat+(urm-prec); // pt strict descrescator   mintaiat=mintaiat+(urm-prec)+1;

           urm=urm-(urm-prec);    // pt strict descrescator   urm=urm-((urm-prec)+1);

       }

       prec=urm;

   }

   fout << taiati << " " << mintaiat;

   return 0;

}