Cod sursa(job #2630867)

Utilizator AokijiAlex M Aokiji Data 27 iunie 2020 16:29:14
Problema Barman Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <deque>
#include <limits>

using namespace std;

int main()
{
    ifstream cin("barman.in");
    ofstream cout("barman.out");
    int n;
    cin >> n;
    vector<int> v(n);
    set<int> s;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        s.insert(v[i]);
    }

    vector<int> sov(s.begin(),s.end());
    vector< vector<int> > who(s.size(),vector<int>());
    for (int i = 0; i < n; i++) {
        v[i] = lower_bound(sov.begin(),sov.end(),v[i]) - sov.begin();
        who[v[i]].push_back(i);
    }

    vector< deque<int> > m(who.size());
    for (int i = 0, k = 0; i < (int)m.size(); i++) {
        for (int j = 0; j < (int)who[i].size(); j++) {
            m[i].push_back(k++);
        }
    }


    int ans = numeric_limits<int>::max();
    for (int i = 0; i < n; i++) {
        int ret = 0;
        for (int j = 0; j < (int)m.size(); j++) {
            for (int k = 0;k <(int)m[j].size(); k++) {
               if (m[j][k] != who[j][k]) {
                     ret += 20 + abs(m[j][k] - who[j][k]);
               } else {

               }
                m[j][k]++;
            }

            if (m[j].back() == n) {
                m[j].pop_back();
                m[j].push_front(0);
            }
        }

        ans = min(ans,ret);
    }


    cout << ans;
    return 0;
}