Pagini recente » Cod sursa (job #155030) | Cod sursa (job #1435796) | Cod sursa (job #1999816) | Cod sursa (job #1101194) | Cod sursa (job #3357157)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
ifstream fin("barman.in");
ofstream fout("barman.out");
int N;
if (!(fin >> N)) return 0;
vector<int> v(N + 1);
vector<int> sortat(2 * N + 1); // Îl dimensionăm dublu pentru circularitate simplă
for (int i = 1; i <= N; ++i) {
fin >> v[i];
sortat[i] = v[i];
}
// Sortăm elementele pentru a avea ordinea crescătoare de bază
sort(sortat.begin() + 1, sortat.begin() + N + 1);
// Dublăm vectorul sortat pentru a simula rotația circulară fără operatorul %
for (int i = 1; i <= N; ++i) {
sortat[N + i] = sortat[i];
}
const int INF = 1e9; // O valoare suficient de mare pentru minimizare
int min_timp_total = INF;
// Testăm toate cele N configurații țintă posibile (fiecare rotație)
for (int start = 1; start <= N; ++start) {
// used[j] va fi 1 dacă poziția j din fereastra curentă a fost deja ocupată
vector<int> used(N + 1, 0);
// PASUL 1: Tratăm cazul particular (elementele deja așezate corect)
// Dacă paharul de pe poziția i corespunde deja ca valoare cu ținta, îl lăsăm pe loc
for (int i = 1; i <= N; ++i) {
if (v[i] == sortat[start + i - 1]) {
used[i] = 1; // Blocăm poziția din țintă, nu o va folosi nimeni altcineva
}
}
int timp_curent = 0;
// PASUL 2: Potrivim Greedy restul paharelor
for (int i = 1; i <= N; ++i) {
// Dacă elementul actual este deja la locul lui, trecem mai departe
if (v[i] == sortat[start + i - 1]) {
continue;
}
// Căutăm prima poziție liberă j în configurația țintă care are aceeași valoare
for (int j = 1; j <= N; ++j) {
if (used[j] == 0 && v[i] == sortat[start + j - 1]) {
used[j] = 1; // Rezervăm această destinație
// Adăugăm costul: 20s (luat + pus jos) + distanța liniară parcursă
timp_curent += abs(i - j) + 20;
break; // Am găsit destinația pentru paharul i, trecem la paharul i + 1
}
}
}
// Reținem costul minim dintre toate rotațiile
min_timp_total = min(min_timp_total, timp_curent);
}
fout << min_timp_total << "\n";
fin.close();
fout.close();
return 0;
}