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

Бсылка Π½Π° Π·Π°Π΄Π°Ρ‡Ρƒ β€” 3356. Zero Array Transformation II.

πŸ“ ОписаниС Π·Π°Π΄Π°Ρ‡ΠΈ

Π”Π°Π½ массив nums Π΄Π»ΠΈΠ½Ρ‹ N ΠΈ список запросов queries, ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… задаётся ΠΊΠ°ΠΊ [li, ri, vali]. Запрос ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ значСния Π² Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π΅ [li, ri] ΠΌΠΎΠΆΠ½ΠΎ ΡƒΠΌΠ΅Π½ΡŒΡˆΠΈΡ‚ΡŒ Π½Π° любоС число ΠΎΡ‚ 0 Π΄ΠΎ vali нСзависимо Π΄Ρ€ΡƒΠ³ ΠΎΡ‚ Π΄Ρ€ΡƒΠ³Π°.

НуТно Π½Π°ΠΉΡ‚ΠΈ минимальноС число ΠΏΠ΅Ρ€Π²Ρ‹Ρ… запросов k, послС ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… nums ΠΌΠΎΠΆΠ΅Ρ‚ прСвратится Π² массив, состоящий Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΈΠ· Π½ΡƒΠ»Π΅ΠΉ. Если это Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ β€” Π²Π΅Ρ€Π½ΡƒΡ‚ΡŒ -1.

πŸ’‘ ИдСя

ВмСсто Ρ‚ΠΎΠ³ΠΎ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΈΠ·ΠΌΠ΅Π½ΡΡ‚ΡŒ nums Π½Π°ΠΏΡ€ΡΠΌΡƒΡŽ, Π±ΡƒΠ΄Π΅ΠΌ Ρ…Ρ€Π°Π½ΠΈΡ‚ΡŒ массив ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΉ ΠΊ Π΄Π΅ΠΊΡ€Π΅ΠΌΠ΅Π½Ρ‚Ρƒ (updates). Он позволяСт эффСктивно ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π½Ρ‹Π΅ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ Π±Π΅Π· Π»ΠΈΡˆΠ½ΠΈΡ… вычислСний.

Π§Ρ‚ΠΎΠ±Ρ‹ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ количСство ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚Π°Π½Π½Ρ‹Ρ… запросов, Π±ΡƒΠ΄Π΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΆΠ°Π΄Π½ΡƒΡŽ ΡΡ‚Ρ€Π°Ρ‚Π΅Π³ΠΈΡŽ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ запросов:

βš™οΈ Π”Π΅Ρ‚Π°Π»ΠΈ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Π°

  1. Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌ массив updates (N+1 элСмСнтов), Π³Π΄Π΅ updates[i] Ρ…Ρ€Π°Π½ΠΈΡ‚ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ измСнСния ΠΊ Π΄Π΅ΠΊΡ€Π΅ΠΌΠ΅Π½Ρ‚Ρƒ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ.
  2. Π˜Ρ‚Π΅Ρ€ΠΈΡ€ΡƒΠ΅ΠΌΡΡ ΠΏΠΎ nums, примСняя Π½Π°ΠΊΠΎΠΏΠ»Π΅Π½Π½Ρ‹Π΅ измСнСния ΠΊ Π΄Π΅ΠΊΡ€Π΅ΠΌΠ΅Π½Ρ‚Ρƒ.
  3. Если nums[i] остаётся ΠΏΠΎΠ»ΠΎΠΆΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ, ΠΆΠ°Π΄Π½ΠΎ Π±Π΅Ρ€Ρ‘ΠΌ запросы ΠΈΠ· списка.
  4. Π’ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅ΠΌ количСство ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Π½Π½Ρ‹Ρ… запросов ΠΈΠ»ΠΈ -1, Ссли массив Π½Π΅ ΡƒΠ΄Π°Π»ΠΎΡΡŒ ΠΎΠ±Π½ΡƒΠ»ΠΈΡ‚ΡŒ.

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

πŸ’» Π˜ΡΡ…ΠΎΠ΄Π½Ρ‹ΠΉ ΠΊΠΎΠ΄

impl Solution {
    pub fn min_zero_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
        let mut updates = vec![0; nums.len() + 1]; // Tracks decrement changes over the range
        let mut queries = queries.into_iter(); // Efficiently consume queries
        let mut processed_queries = 0;

        let mut accumulated_decrement = 0;
        for (i, num) in nums.into_iter().enumerate() {
            // Process queries until we can make nums[i] zero
            while num > accumulated_decrement + updates[i] {
                if let Some(q) = queries.next() {
                    let (left, right, decrement) = (q[0] as usize, q[1] as usize, q[2]);

                    if i <= right {
                        updates[right + 1] -= decrement;
                        updates[left.max(i)] += decrement;
                    }
                    processed_queries += 1;
                } else {
                    return -1; // No more queries left to process
                }
            }
            accumulated_decrement += updates[i];
        }

        processed_queries
    }
}

Tags: #rust #algorithms #greedy