Chương trình Python đếm số block được đi qua k lần khi di chuyển

Cho danh sách walks biểu thị các bước di chuyển trên đường thẳng 1 chiều (bắt đầu từ vị trí 0). Giá trị dương = đi phải, âm = đi trái. Mỗi bước di chuyển 1 đơn vị (block). Cần tìm số block được đi qua ít nhất target lần.

Ví dụ

walks = [3, -7, 2], target = 2 → Output: 5

Các block được đi qua 2 lần: [0,1], [1,2], [2,3], [-4,-3], [-3,-2].

Thuật toán (Line Sweep / Difference Array)

1. Dùng Difference Array (jumps) để đánh dấu bắt đầu/kết thúc đoạn đi.
2. Duyệt walks: tại vị trí hiện tại pos, tăng +1 (đi phải) hoặc -1 (đi trái); tại pos + dist giảm tương ứng.
3. Sắp xếp các key của jumps, duyệt tính prefix sum (level) - số lần đi qua.
4. Khi level >= target, cộng độ dài đoạn vào total.

Code Python

from collections import defaultdict

def solve(walks, target):
    pos = 0
    jumps = defaultdict(int)
    
    # Xây dựng difference array
    for dist in walks:
        if dist > 0:
            jumps[pos] += 1
            jumps[pos + dist] -= 1
        else:
            jumps[pos] -= 1
            jumps[pos + dist] += 1
        pos += dist
    
    # Line sweep
    lastpos = level = total = 0
    for pos, val in sorted(jumps.items()):
        if level >= target:
            total += pos - lastpos
        level += val
        lastpos = pos
    
    return total

# Test
walks = [3, -7, 2]
target = 2
print(solve(walks, target))  # 5

Giải thích chi tiết

Bước 1: Xây dựng jumps

walks = [3, -7, 2]
pos=0: dist=3  -> jumps[0]+=1, jumps[3]-=1   pos=3
pos=3: dist=-7 -> jumps[3]-=1, jumps[-4]+=1  pos=-4
pos=-4: dist=2 -> jumps[-4]+=1, jumps[-2]-=1 pos=-2

jumps = {0:1, 3:0, -4:2, -2:-1}  # sau khi gộp

Bước 2: Line sweep (sorted keys: -4, -2, 0, 3)

pos=-4, val=2: level=0<2 -> level=2, lastpos=-4
pos=-2, val=-1: level=2>=2 -> total+=2, level=1, lastpos=-2
pos=0, val=1: level=1<2 -> level=2, lastpos=0
pos=3, val=0: level=2>=2 -> total+=3, level=2, lastpos=3
total = 2 + 3 = 5

Độ phức tạp

• Thời gian: O(n log n) do sort (n = len(walks)).
• Không gian: O(n) cho dictionary jumps.