Cod sursa(job #2006928)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 1 august 2017 14:12:18
Problema Barman Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
/*
Sortez vectorul si generez permutarile circulare.
Elementele care sunt pe aceeasi poz raman unde sunt.
De asemenea se observa ca nu are rost sa port 2 pahare pe tava in acelasi timp.
Pt restul elementelor gasesc masa cu cel mai mic indice neocupata, deoarece nu influenteazasuma finala a timpilor.
Suma finala este influentata doar de mesele si paharele care sunt aranjate, nu si de valoarea paharelor.
*/
#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;
ifstream fi("barman.in");
ofstream fo("barman.out");
int n,i,j,rez,A[1201],B[601],timp;
queue<int> M,P;
int main()
{
    fi>>n;
    for(i=1; i<=n; i++)
    {
        fi>>A[i];
        B[i]=A[i];
    }
    sort(A+1,A+n+1);
    for(i=1; i<n; i++)
    {
        A[n+i]=A[i];
    }
    rez=1000000000;
    for(i=1; i<=n; i++)
    {
        timp=0;
        for(j=1; j<=n; j++)
        {
            if(B[j]!=A[i+j-1])
            {
                if(!M.empty())
                {
                    timp=timp+j-M.front()+20;
                    M.pop();
                    if(!P.empty())
                    {
                        timp=timp+j-P.front()+20;
                        P.pop();
                    }
                    else
                    {
                        M.push(j);
                    }
                }
                else
                {
                    P.push(j);
                    M.push(j);
                }
            }
        }
        while(!M.empty())
            M.pop();
        while(!P.empty())
            P.pop();
        rez=min(rez,timp);
    }
    fo<<rez<<"\n";
    fi.close();
    fo.close();
    return 0;
}