Untitled
unknown
plain_text
6 months ago
2.8 kB
4
Indexable
import java.util.*; public class q2part { // Maksimum karı hesaplamak için kullanılan fonksiyon public static int maxProfit(int numLiquids, int numConversions, int[] prices, List<int[]> conversions) { // Sıvı türleri arasındaki dönüşümleri temsil etmek için bir graf oluşturun List<List<Integer>> graph = new ArrayList<>(); // Grafın her sıvı için boş bir komşu listesi olacak şekilde başlatılması for (int i = 0; i < numLiquids; i++) { graph.add(new ArrayList<>()); } // Geçişleri graf yapısına ekleyin for (int[] conversion : conversions) { int from = conversion[0] - 1; // Dizi 0 tabanlı, bu yüzden -1 yapıyoruz int to = conversion[1] - 1; graph.get(from).add(to); } // Başlangıçta maksimum fiyatları mevcut fiyatlara eşitleyin int[] maxPrices = Arrays.copyOf(prices, numLiquids); // Bellman-Ford algoritmasını kullanarak maksimum fiyatları güncelleyin for (int i = 0; i < numLiquids - 1; i++) { for (int u = 0; u < numLiquids; u++) { for (int v : graph.get(u)) { // Eğer u'dan v'ye geçiş varsa, v'nin fiyatını güncelleyin if (maxPrices[v] < maxPrices[u]) { maxPrices[v] = maxPrices[u]; } } } } // Maksimum kar hesaplayın int maxProfit = 0; for (int i = 0; i < numLiquids; i++) { maxProfit = Math.max(maxProfit, maxPrices[i] - prices[i]); } return maxProfit; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // Test durumu sayısını al int testCases = scanner.nextInt(); for (int t = 0; t < testCases; t++) { // Sıvı sayısı ve dönüşüm sayısını al int numLiquids = scanner.nextInt(); int numConversions = scanner.nextInt(); // Sıvı fiyatlarını al int[] prices = new int[numLiquids]; for (int i = 0; i < numLiquids; i++) { prices[i] = scanner.nextInt(); } // Dönüşüm bilgilerini al List<int[]> conversions = new ArrayList<>(); for (int i = 0; i < numConversions; i++) { int from = scanner.nextInt(); int to = scanner.nextInt(); conversions.add(new int[]{from, to}); } // Her test durumu için maksimum karı hesapla ve sonucu yazdır int result = maxProfit(numLiquids, numConversions, prices, conversions); } } }
Editor is loading...
Leave a Comment