Czesc, przygotowuje sie do zawodow w programowaniu zespolowym. Mam problemy z zadaniami optymalizacyjnymi w stylu:
http://zawody.pb.bialystok.pl/2006/index.php?pokaz=historia42
Nie potrafie wymyslic lepszego algorytmu niz BurteForce, oto moj kod:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int stacje[100]; // odleglosci kolejnych stacji od poczatku autostrady
int n; // ilosc stacji
// warsztat - odleglosc od poczatku autostrady stacji, przy ktorej zostanie wybudowany sklad
int Oblicz_odleglosc_od_stacji(int warsztat)
{
int suma = 0;
int i;
for (i = 0; i < n; i++)
suma += abs(stacje[i] - warsztat);
return suma;
}
int main()
{
int i;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &stacje[i]);
int min = Oblicz_odleglosc_od_stacji(stacje[0]); // minimalna suma odleglosci
for (i = 1; i < n; i++)
{
int odl = Oblicz_odleglosc_od_stacji(stacje[i]);
if (odl < min)
min = odl;
}
printf("%d\n", min);
return 0;
}
Chcialem zapytac, czy mozna wymislic do tego typu zadan jakis lepszy algorytm, i poprosic o pomoc w zaprojektowaniu takiego.