Fabryka butów ( omówienie )

08.08.2010

Wiadomo, że fabryka nigdy nie będzie stratna, gdyż można ustalić cene na N+1 i zysk fabryki wyniesie 0.

Wystarczy sprawdzać ceny całkowite, gdyż liczba osób, która kupi buty po cenie X będzie taka sama jak liczba osób, która kupi buty po cenie sufit(X). Należało obliczyć ile osób kupi buty, gdy te będą kosztowały k dla każdego k z przedziału [1,N]. Trzeba było zauważyć że liczba_sprzedanych_butów(CENA) = A[CENA] + liczba_sprzedanych_butów[CENA+1]. Poniżej przykładowe rozwiązanie.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include 
#include 
 
int A[100010];
 
int main(){
        int test,N, koszt_produkcji_buta;
        scanf("%d",&test);
        while(test--){
                scanf("%d %d",&N,&koszt_produkcji_buta);
                for(int i=1; i<=N; i++)
                        scanf("%d",&A[i]);
                
                long long ilosc = 0;
                long long zysk = 0;
                long long wynik = 0;
                
                for(int i=N; i>=1; i--){
                        ilosc += A[i];
                        zysk = ilosc * i;
                        wynik = std::max(wynik, zysk - ilosc * koszt_produkcji_buta);    
                }
                
                printf("%lld\n",wynik);
        }
        return 0;
}

 

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com