Question

pbinfo #1877 Greedy
Se dă un șir cu n elemente, numere întregi, și un număr natural k ≤ n. Calculați cea mai mare sumă care poate fi obținută schimbând semnul a exact k elemente aflate pe poziții distincte din șirul dat.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului, apoi numărul k.

Date de ieșire
Programul va afișa pe ecran numărul S, reprezentând suma maximă determinată.

Restricții și precizări
1 ≤ n ≤ 1000
elementele șirului vor fi cuprinse între -1.000.000 și 1.000.000

Answer 1

#include <iostream>

using namespace std;

int n,k,a[1001],i,minim,maxim,j,S;

int main()
{

    cin >> n;

    for(i=1;i<=n;i++)
     cin >> a[i];

    cin >>k;

    minim=a[1];
    maxim=a[1];

    for(i=1;i<=n;i++)
    {
        if(a[i]<minim) minim=a[i];
        if(a[i]>maxim) maxim=a[i];
    }

   while(j<=k)
    for(minim=minim;minim<=maxim;minim++)
     for(i=1;i<=n;i++)
      if(minim==a[i])
             {
                  j++;
                  if(j<=k)
                   a[i]=-a[i];

             }



    for(i=1;i<=n;i++)
     S+=a[i];

    cout << S;

    return 0;
}