Question

Język c++, dam naj

Chcesz zrobić zakupy. Wiesz dokładnie, jakie produkty chcesz kupić. Sprawdziłeś już w Internecie ceny każdego
z produktów we wszystkich okolicznych marketach. Masz czas pojechać do co najwyżej dwóch marketów
i łącznie chcesz w nich kupić po jednym egzemplarzu każdego produktu. Jak to zrobić najtaniej?
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite n oraz m (2 ≤ n, m ≤ 100) oddzielone spacją, oznaczające
liczbę marketów oraz liczbę produktów, które chcesz kupić. Każdy z kolejnych n wierszy zawiera po m liczb
całkowitych z zakresu od 1 do 1000. Pierwszy wiersz zawiera ceny kolejnych produktów w pierwszym markecie,
drugi – ceny kolejnych produktów w drugim markecie itd.
Wyjście
Twój program powinien wypisać jedną liczbę całkowitą: minimalny koszt zakupu wszystkich potrzebnych
produktów w co najwyżej dwóch marketach.
Przykład
Dla danych wejściowych:
3 4
7 3 7 9
2 20 10 6
8 8 8 8
poprawnym wynikiem jest:
18
Wyjaśnienie do przykładu: Najlepiej pojechać do pierwszego i drugiego marketu. W pierwszym kupujemy
drugi i trzeci produkt (koszt 3 + 7), a w drugim pierwszy i czwarty (koszt 2 + 6).

Answer 1

Odpowiedź:

Oto przykładowy kod w języku C++, który rozwiązuje ten problem:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

vector<vector<int>> prices(n, vector<int>(m));

// Wczytanie cen produktów ze wszystkich marketów

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

cin >> prices[i][j];

}

}

int cheapest = 1e9; // Najniższa cena, która została znaleziona

// Przeglądanie wszystkich kombinacji dwóch marketów

for (int i = 0; i < n; i++) {

for (int j = i + 1; j < n; j++) {

int cost = 0;

// Obliczanie kosztu zakupów w obu marketach

for (int k = 0; k < m; k++) {

cost += min(prices[i][k], prices[j][k]);

}

// Aktualizacja najniższej ceny, jeżeli ta kombinacja jest tańsza

cheapest = min(cheapest, cost);

}

}

cout << cheapest << endl;

return 0;

}

Program najpierw wczytuje dwie liczby całkowite `n` i `m`, oznaczające liczbę marketów i liczbę produktów, które chcemy kupić. Następnie wczytuje ceny produktów ze wszystkich marketów do wektora `prices`.

Program przegląda wszystkie kombinacje dwóch marketów i oblicza koszt zakupów w każdej z nich. Aktualizuje najniższą cenę, jeśli ta kombinacja jest tańsza.

Na końcu program wypisuje najniższą cenę, jaką można osiągnąć.