Adayları iki şehir arasında böl
Görev tanımı
Problem
Bir şirket çift sayıda adayı yerinde mülakatlara uçuruyor ve tam yarısı A ofisine, yarısı B ofisine gitmeli. costs[i] = [a, b], i adayının her ofise uçuş ücretini veriyor. Adayların tam yarısını her ofise gönderen en düşük toplam ücreti döndür.
Örnekler
Input: costs = [[10, 20], [30, 200], [400, 50], [30, 20]]
Output: 110
Neden: ilk ikisi 10 + 30 ile A'ya, son ikisi 50 + 20 ile B'ye gider
Input: costs = [[259, 770], [448, 54], [926, 667], [184, 139], [840, 118], [577, 469]]
Output: 1859
Input: costs = [[5, 5], [7, 7]]
Output: 12
Neden: edge case: iki ofis de aynı tutuyor, yani herhangi bir eşit bölünme optimal
İpuçları
0 / 3
Herkesi ucuz ofisine göndermek, çok fazla kişi aynı ofisi tercih ettiğinde başarısız olur. Bir adayı A'dan B'ye taşımanın neye mal olduğunu düşün.
i adayını A'dan B'ye taşımak toplamı b eksi a kadar değiştirir. A'ya uçarak en çok tasarruf edenler A'yı alanlar olmalı.
Adayları a eksi b'ye göre, en negatiften en pozitife sırala. İlk yarıyı A'ya, ikinci yarıyı B'ye gönder ve ücretleri topla.
- Hedef zaman
- O(n log n)
- Hedef alan
- O(n)
Kısıtlar
- the number of candidates is even
Çözüm
Önce herkesin B'ye uçtuğunu düşün; i adayını A'ya geçirmek toplamı a eksi b kadar değiştirir ve adayların tam yarısı geçmelidir. Onları seçmenin en ucuz yolu a eksi b değerleri en küçük olan yarıyı almaktır; bu yüzden liste bu farka göre sıralanır ve ortadan bölünür. Bir exchange argument bunu doğrular: bir A adayını farkı daha küçük bir B adayıyla değiştirmek toplamı yalnız düşürebilirdi. Sıralama için zaman O(n log n), sıralı kopya için alan O(n).
def split_cities(costs):
costs = sorted(costs, key=lambda c: c[0] - c[1]) # most eager for A first
half = len(costs) // 2
return sum(a for a, _ in costs[:half]) + sum(b for _, b in costs[half:])
print(split_cities([[10, 20], [30, 200], [400, 50], [30, 20]])) # -> 110
print(split_cities([[259, 770], [448, 54], [926, 667], [184, 139], [840, 118], [577, 469]])) # -> 1859
print(split_cities([[5, 5], [7, 7]])) # -> 12Kodda değil de fikirde mi takıldın? Sıralama temelleri bunu anlatıyor.