maksymalny algorytm zarobkowania

Question

Jak mogę obliczyć maksymalne zarobione pieniądze z m biletów w oknach z biletami, że cena biletu jest równa liczbie losów biletów w tym oknie?

Na dworcu kolejowym znajduje się n okien biletowych. Okno z ma dostępne bilety (j). Cena biletu jest równa liczbie biletów pozostałych w tym oknie w tym czasie. Jaka jest maksymalna kwota, jaką dana stacja kolejowa może zarobić ze sprzedaży pierwszych m biletów?

Na przykład, jeśli mamy 3 okna biletowe, mamy bilety 3, 3, 4 i chcemy sprzedać 5 biletów. Następnie:

n = 3, m = 5 
A[3] = {3, 3, 4} 

Maksymalna zarobione pieniądze jest 4 + 3 + 3 + 3 + 2 = 15

Widziałem to pytanie online i moje rozwiązanie jest najpierw wcisnąć wszystkie bilety numerów do maxHeap i uruchomić dla pętli dla m razy. Za każdym razem, gdy pobieramy najwyższą wartość maxHeap i dodajemy do całkowitej zarobionej kwoty, a jeśli wartość jest większa niż 1, wciskamy (wartość - 1) do maxHeap.

Ale to jest zbyt czasochłonne lepsze rozwiązania?

Answer 1

Aby rozwiązać ten problem, musimy dokonać obserwacji:

• Aby uzyskać maksymalny efekt, musimy dostać się na najwyższym m bilety.

Let x być maksymalna liczba biletów pozostawione w oknie, więc pieniądze jedno okno i przyczynia się do całkowitego wynagrodzenia jest

(a(i) + a(i) - 1 + ... + x + 1) = a(i)*(a(i) + 1)/2 - x*(x + 1)/2 

Aby znaleźć x, możemy użyć binarne wyszukiwania

int start = 0; 
int end = maximum number of ticket in one window; 
while(start <= end) 
    int mid = (start + end)/2; 
    for(each window) 
     number of sell ticket += a(i) - mid;//if mid is larger than a(i), just add a zero 
    if(number of sell ticket >= m) 
     increase start; 
    else 
     decrease end; 

Zatem złożoność czasu to O (n log m) z n jest liczbą okien, a m jest maksymalną liczbą biletów w jednym oknie.

Answer 2

Jeśli używasz maks. Sterty, można to zrobić w O (m * logn). Oto kod C++ -

int main() { 
     int *inputArray; 
     int n; 
     int m; 
     cin >> n; 
     cin >> m; 
     inputArray = new int[n]; 
     for (int i = 0; i < n; i++) { 
      cin >> inputArray[i]; 
     } 
     cout << maximize(inputArray, n, m) << "\n"; 

     return 0; 
    } 

int maximize(int *inputArray, int n, int m){ 

     vector<int> v(inputArray, inputArray + n); 
     int sum = 0; 

     // make max heap 
     make_heap(v.begin(), v.end()); 

     for (m = 4; m != 0; m--) { 
      // get max value 
      int max = v.front(); 

      // move max value to end and heapify 
      pop_heap(v.begin(), v.end()); 
      // pop it out 
      v.pop_back(); 

      sum = sum + max; 

      if (max - 1) { 
       // insert m-1 into vector 
       v.push_back(max - 1); 
       // heapify the new vector 
       push_heap(v.begin(), v.end()); 
      } 
     } 

     return sum; 
    } 

Answer 3

 package package1; 
import java.util.Arrays; 
import java.util.Scanner; 

public class RailwayStation{ 
    int numOfTickets, ticketsToSell; 
    int[] ticketsPerBooth; 

    public RailwayStation(int numOfTickets, int ticketsToSell, int[] ticketsPerBooth) 
    { 
     this.numOfTickets = numOfTickets; 
     this.ticketsToSell = ticketsToSell; 
     this.ticketsPerBooth = ticketsPerBooth; 
    } 

    public int findMaxRevenue() 
    { 
     int[] perBooth = this.ticketsPerBooth; 
     Arrays.sort(perBooth); 
     int i = perBooth.length-1; 
     int revenue = 0; 
     while(i>=0 && ticketsToSell!=0){ 

      int diff = 0; 
      if(i==0){ 

       diff = 1; 
      }else{ 
       diff = perBooth[i] - perBooth[i-1]; 
      } 

      while(diff!=0 && ticketsToSell!=0){ 

       revenue = revenue + perBooth[i]; 
       perBooth[i]--; 
       diff--; 
       ticketsToSell--; 

      } 
      if(ticketsToSell!=0 && i==0){ 
       i = perBooth.length-1; 
      }else{ 
       i--; 
      } 


     } 
     return revenue; 
    } 

    public static void main(String[] args) 
    { 
     Scanner sc = new Scanner(System.in); 
     int numOfBooths = sc.nextInt(); 
     int ticketsToSell = sc.nextInt(); 
     int perBooth[] = new int[numOfBooths]; 
     for(int i = 0; i < numOfBooths; i++) 
     { 
      perBooth[i] = sc.nextInt(); 
     } 
     RailwayStation rt = new RailwayStation(numOfBooths, ticketsToSell, perBooth); 
     System.out.println("Max Revenue = " + rt.findMaxRevenue()); 
    } 
} 

Answer 4

"" "zmodyfikowany silnia że podsumowuje do granicy indeksu rundy" ""

def modified_fact (limit, liczba): sum_fact = 0 for i in range (numer - przekroczony limit + 1, liczba + 1): sum_fact + = i powrócić sum_fact

''” mam oblicza ile rund musiałbym zrobić, aby zmniejszyć. I w ostatniej iteracji do jakiego indeksu będę potrzebował do iteracji.

''”

def maximum_earning_algorithm (N, okien) ""”

:param windows: 
:param n: 
:rtype: int 
""" 
money = 0 
final_round_limit_index = n % len(windows) 
rounds = n/(len(windows)) 
print final_round_limit_index, rounds 
for i in range(len(windows)): 
    if i < final_round_limit_index: 
     money += modified_fact(rounds + 1, windows[i]) 
    else: 
     money += modified_fact(rounds, windows[i]) 
return money 

jeśli nazwa == główny ' okno = [5, 4, 3] print maximum_earning_algorithm (3, window)

Answer 5

Podejście 1)
As @ n.m. wskazał na niewielki optymalizacja rozwiązania MaxHeap:

Nie trzeba usunąć bilety, jeden po drugim. Jeśli masz najwyższe okno, musisz wiedzieć, ile biletów posiada i ile biletów ma następny. Następnie możesz usunąć różnicę i obliczyć łączną cenę w jednej operacji. Przy niewielkich modyfikacjach możesz zrobić to samo, jeśli masz kilka okien z taką samą maksymalną liczbą biletów.

---

Sposób 2) z użyciem posortowanej tablicy:

obciążenia okna w tablicy. Sortuj tablicę. Przejdź wstecz przez tablicę i jak to robisz: zapisz tę liczbę (bieżącą), dodaj ją do agregatora, przejdź do następnej wartości. Jeśli jest taki sam (bieżący), dodaj go do agregatora, odejmij 1 od niego, kontynuuj. Jeśli jest inaczej, wróć do końca tablicy i zacznij od nowa. Zrób to N razy (pętla wewnętrzna, a nie zewnętrzna).

---

Metoda 3) za pomocą tablicy licznika (liniowy Złożoność)

1. Tworzenie tablicę z indeksem jako NO. biletów i wartości jak nie. straganów posiadających tyle biletów. Tak więc {0-> 0, 1> 1, 2> 0, 3> 2} oznacza, że ​​1 stoisko ma 1 bilet, a 2 stoły mają 3 bilety)

2. Zacznij od najwyższego indeksu tablicy (liczba 1) i dodać, że indeks czytniku (a) tak, a = 3, a następnie redukcji, że wskaźnik (3) 1 do 1 oraz zwiększenie wskaźnika poniżej (= 2) 1 do 1.
   Tablica jest { 0,1,1,1} i A = 3. Powtarzać. A = 6, tablica to {0,1,2,0}. Ostatni wskaźnik wynosi zero, więc przesuń wskaźnik do wskaźnika 2.
   Repeat, więc A = 8, array = {0,2,1,0}. Powtarzać. A = 10, tablica to {0,5,0,0}. (. Do liczby sprzedanych biletów)
   Zatrzymaj kiedy zrobiłeś to t razy

Oto realizacja tego podejścia:

int[] stalls = new int[] { 3,1,3 }; // 2 stalls have 3 tickets each and 1 stall have 1 ticket 
     int t = 4; 

     Arrays.sort(stalls); 

     int tickets = stalls[stalls.length - 1]; 
     int[] dp = new int[tickets + 1]; 

     for (int i = 0; i < stalls.length; i++) { 
      dp[stalls[i]]++; 
     } 

     int total = 0; 
     int i = dp.length - 1; 

     while (t > 0) { 
      if (dp[i] > 0) { 
       total += i; 
       t--; 
       dp[i]--; 
       dp[i - 1]++; 
      } else { 
       i--; 
      } 
     } 

     System.out.println(total);