главная Π½ΠΎΠ²ΠΎΠ΅ Π»ΡƒΡ‡ΡˆΠ΅Π΅ Π½Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ

Бсылка Π½Π° Π·Π°Π΄Π°Ρ‡Ρƒ β€” 2594. Minimum Time to Repair Cars.

❓ ОписаниС Π·Π°Π΄Π°Ρ‡ΠΈ

Π”Π°Π½ΠΎ:

НуТно Π½Π°ΠΉΡ‚ΠΈ минимальноС врСмя, Π·Π° ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ всС ΠΌΠ°ΡˆΠΈΠ½Ρ‹ Π±ΡƒΠ΄ΡƒΡ‚ ΠΎΡ‚Ρ€Π΅ΠΌΠΎΠ½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Ρ‹.
ΠŸΡ€Π΅Π΄ΠΏΠΎΠ»Π°Π³Π°Π΅Ρ‚ΡΡ, Ρ‡Ρ‚ΠΎ всС ΠΌΠ΅Ρ…Π°Π½ΠΈΠΊΠΈ Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‚ ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ.

πŸ’‘ ИдСя

ΠœΠ΅Ρ…Π°Π½ΠΈΠΊΠΈ с мСньшим Ρ€Π°Π½Π³ΠΎΠΌ Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‚ быстрСС.
ΠŸΡ€ΠΎΠΈΠ·Π²Π΅Π΄Ρ‘ΠΌ ΠΏΠ΅Ρ€Π²ΠΈΡ‡Π½ΠΎΠ΅ распрСдСлСниС машин, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ ΠΎΠ±Ρ€Π°Ρ‚Π½Ρ‹ΠΉ ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚Π½Ρ‹ΠΉ ΠΊΠΎΡ€Π΅Π½ΡŒ Ρ€Π°Π½Π³Π° ΠΊΠ°ΠΊ вСс, ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‰ΠΈΠΉ долю машин, ΠΏΠ΅Ρ€Π΅Π΄Π°Π½Π½Ρ‹Ρ… ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡƒ ΠΌΠ΅Ρ…Π°Π½ΠΈΠΊΡƒ.

Однако это распрСдСлСниС Π½Π΅ ΠΏΠΎΠΊΡ€Ρ‹Π²Π°Π΅Ρ‚ всС ΠΌΠ°ΡˆΠΈΠ½Ρ‹. Для распрСдСлСния ΠΎΡΡ‚Π°Π²ΡˆΠΈΡ…ΡΡ машин ΠΌΡ‹ посчитаСм для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΌΠ΅Ρ…Π°Π½ΠΈΠΊΠ° ΠΎΡ†Π΅Π½ΠΊΡƒ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ Π΅Π³ΠΎ Ρ€Π°Π±ΠΎΡ‚Ρ‹, Ссли Π²Π·ΡΡ‚ΡŒ нСсколько Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… машин (Ρ‚Π΅ΠΌ большС, Ρ‡Π΅ΠΌ большС вСс ΠΌΠ΅Ρ…Π°Π½ΠΈΠΊΠ°). ПослС остаётся лишь Π²Ρ‹Π±Ρ€Π°Ρ‚ΡŒ k-ΠΎΠ΅ минимальноС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ срСди посчитанных Π²Ρ€Π΅ΠΌΡ‘Π½ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Β«QuickSelectΒ» (любСзно Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π² стандартной Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠ΅ Rust).

πŸ” Π”Π΅Ρ‚Π°Π»ΠΈ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Π°

1️⃣ БыстроС распрСдСлСниС β€” вычисляСм вСс ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΌΠ΅Ρ…Π°Π½ΠΈΠΊΠ° ΠΈ распрСдСляСм ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ.
2️⃣ Π”ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ ΠΎΡ†Π΅Π½ΠΊΠΈ β€” для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΌΠ΅Ρ…Π°Π½ΠΈΠΊΠ° прСдвычисляСм Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ Π²Ρ€Π΅ΠΌΠ΅Π½Π° Ρ€Π΅ΠΌΠΎΠ½Ρ‚Π° (согласно вСсу ΠΌΠ΅Ρ…Π°Π½ΠΈΠΊΠ°).
3️⃣ Π’Ρ‹Π±ΠΎΡ€ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ β€” примСняСм ΠΌΠ΅Ρ‚ΠΎΠ΄ ΠΈΠ· стандартной Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠΈ select_nth_unstable, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π½Π°ΠΉΡ‚ΠΈ Π½Π°ΠΈΠ»ΡƒΡ‡ΡˆΠ΅Π΅ врСмя Ρ€Π΅ΠΌΠΎΠ½Ρ‚Π° нСраспрСдСлённых ΠΈΠ·Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎ машин.

⏳ Асимптотика

Π—Π°ΠΌΠ΅Ρ‡Π°Π½ΠΈΠ΅

Π£ мСня Π½Π΅Ρ‚ Ρ‡Ρ‘Ρ‚ΠΊΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π° Π΄ΠΎΠΊΠ°Π·Π°Ρ‚Π΅Π»ΡŒΡΡ‚Π²Π° коррСктности эвристики с прСдрасчётом Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… машин для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΈΠ· ΠΌΠ΅Ρ…Π°Π½ΠΈΠΊΠΎΠ². Но Π½Π° всСх Ρ€Π°Π·ΡƒΠΌΠ½Ρ‹Ρ… ΠΌΠΎΠΈΡ… тСстах ΠΈ тСстах с LeetCode эвристика ΡƒΡΠΏΠ΅ΡˆΠ½ΠΎ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚!

πŸ“ Π˜ΡΡ…ΠΎΠ΄Π½Ρ‹ΠΉ ΠΊΠΎΠ΄

impl Solution {
    pub fn repair_cars(ranks: Vec<i32>, mut cars: i32) -> i64 {
        // Normalization factor to weight mechanics by inverse square root of ranks.
        let weights_normalize: f64 = 1.0 / ranks.iter()
            .map(|&rank| (1.0 / rank as f64).sqrt())
            .sum::<f64>();

        let total_cars = cars as f64;
        let total_mechanics = ranks.len() as f64;
        let mut max_time = 0i64;
        let mut next_times = Vec::new();

        // Quickly assign cars based on mechanic ranks (weighted by inverse square root of rank).
        for &rank in &ranks {
            let weight = (1.0 / rank as f64).sqrt() * weights_normalize;
            let assigned = (total_cars * weight) as i32;
            cars -= assigned;

            let time = Self::repair_time(rank, assigned);
            max_time = max_time.max(time);

            // Determine the number of additional cars dynamically based on weight
            let additional_cars = (total_mechanics * weight).ceil() as i32; // Adjusted heuristic for next times
            for offset in 1..=additional_cars {
                next_times.push(Self::repair_time(rank, assigned + offset));
            }
        }

        // Determine final max time considering remaining cars
        if cars > 0 {
            let (_, nth_time, _) = next_times.select_nth_unstable(cars as usize - 1);
            max_time = max_time.max(*nth_time);
        }

        max_time
    }

    /// Calculates repair time for a given mechanic rank and number of cars
    fn repair_time(rank: i32, cars: i32) -> i64 {
        rank as i64 * (cars as i64).pow(2)
    }
}

Tags: #rust #algorithms #optimization #heuristics