Treść zadania:
"W szeregu zbiórka!" – krzyknął nauczyciel wychowania fizycznego. Dzieci na rozkaz ustawiły się w szeregu, zachowując odstęp 1 metra, ale zapomniały o porządku reprezentowanej grupy. Patrząc od lewej, najpierw powinna stać grupa Dyniowa, a potem grupa Czekoladowa. Nauczyciel bardzo szybko się denerwuje, dlatego aby uniknąć problemów uczniowie muszą niepostrzeżenie zamienić się miejscami. Akcja będzie przeprowadzona sprawnie, jeśli sumaryczna droga, jaką pokonają dzieci, będzie możliwie najmniejsza.
Wejście:
W pierwszym wierszu standardowego wejścia podano liczbę dzieci w szeregu n (1 6 n 6 106 ). W drugim wierszu znajduje się opis szeregu w postaci n znaków D (osoba z grupy Dyniowej) lub C (osoba z grupy Czekoladowej).
Wyjście:
W pierwszym wierszu standardowego wyjścia powinna znaleźć się minimalna suma odległości, jaką muszą pokonać dzieci, aby poprawnie się ustawić.
Przykłady:
Wejście:
4
CDCC
Wyjście:
2
Mój kod:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,x;
cin>>n;
string litery[n];
for(int i=0;i<n;i++)
{
cin>>litery[i];
}
sort(litery, litery+n);
for(int i=0;i<n;i++)
{
cout<<setw(3)<<litery[i];
}
return 0;
}
Problem:
Jak widać samo sortowanie nie jest problemem, nie wiem jak policzyć drogę, którą muszą przebyć te litery, mógłbyś ktoś dać jakąś wskazówkę?