Mam jeszcze problem z innym zadaniem:
Kupiec
Limit pamięci: 32 MB
Bajtazar jest wędrownym kupcem, który przemieszcza się pomiędzy miastami leżącymi wzdłuż linii kolejowej. Jego cel jest prosty: kupić tanio, sprzedać z zyskiem i nie wydać zbyt dużo na podróż.
Wspomniane miasta są ponumerowane od do zgodnie z kolejnością występowania wzdłuż torów. Bajtazar chciałby zarobić możliwie najwięcej na pewnym konkretnym towarze, którego cenę w każdym mieście zna. Ponadto wie, ile kosztuje przejazd między dowolną parą sąsiadujących miast (droga w okolicy jest tylko jedna, więc bezpośrednio można poruszać się jedynie pomiędzy miastami o numerach oraz ). Jego zysk to cena, po której sprzeda towar, pomniejszona o cenę zakupu i sumaryczny koszt przejazdu. Niestety Bajtazar nie jest zbyt dobry z ekonomii i potrzebuje Twojej pomocy. Napisz program, który obliczy maksymalny możliwy zysk w jednej takiej parze transakcji, zakładając, że Bajtazar może rozpocząć i zakończyć podróż w dowolnych miastach.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę miast. W drugim wierszu znajduje się liczb całkowitych () pooddzielanych pojedynczymi odstępami. Są to ceny towaru w kolejnych miastach. Trzeci wiersz zawiera liczb całkowitych ( dla ) pooddzielanych pojedynczymi odstępami, oznaczających ceny przejazdu odpowiednio między miastami o numerach oraz .
Wyjście
Twój program powinien wypisać na standardowe wyjście jedną liczbę całkowitą - maksymalny możliwy zysk Bajtazara. Zauważ, że w skrajnym przypadku Bajtazar może kupić i sprzedać towar w tym samym mieście.
Przykład
Dla danych wejściowych:
4
19 5 2 3
5 1 1
poprawną odpowiedzią jest:
11
Wyjaśnienie do przykładu: Bajtazar kupuje towar w mieście numer 3 (cena: 2), następnie przejeżdża do miasta numer 1 (koszt tego przejazdu to ), gdzie sprzedaje towar w cenie 19. Łączny zysk Bajtazara to: 11.
Moje rozwiązanie 40/100 :
// ConsoleApplication2.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
long miasta;
//long*ceny_towarow = new long[];
//long*ceny_przejazdu = new long[];
vector <long> ceny_towarow(1000000);
vector <long> ceny_przejazdu(1000000);
long najmniejsze = 1000000000;
long m;
long zysk_lokalny = 0;
void korzysc(vector <long> tab,vector <long> tab1)
{
for (int i = 1; i <= miasta; i++)
{
if (tab[i] < najmniejsze)
{
najmniejsze = tab[i];
m = i;
}
}
long zysk = 0;
long podroz = 0;
for (int i = 1; i <= miasta; i++)
{
podroz = 0;
if (i < m)
{
for (int j = i; j < m; j++)
podroz += tab1[j];
}
else if (i > m)
{
for (int j = m; j < i; j++)
podroz += tab1[j];
}
zysk_lokalny = tab[i] - (podroz + najmniejsze);
if (zysk_lokalny > zysk)
zysk = zysk_lokalny;
}
cout << zysk;
}
int main()
{
cin >> miasta;
for (int i = 1; i <= miasta; i++)
{
cin >> ceny_towarow[i];
}
for (int i = 1; i <= miasta - 1; i++)
{
cin >> ceny_przejazdu[i];
}
korzysc(ceny_towarow, ceny_przejazdu);
return 0;
}
Co powinienem poprawić, bo nie za bardzo wiem?