Giải thuật tối ưu điểm số

Cho mảng số nguyên nums và số nguyên k. Điểm số ban đầu bằng 0. Mỗi thao tác:

1. Chọn chỉ số i hợp lệ
2. Tăng điểm số thêm nums[i]
3. Cập nhật nums[i] = ceil(nums[i] / 3)

Yêu cầu: Tính điểm số tối đa sau đúng k thao tác (hàm ceil(x) trả về số nguyên nhỏ nhất ≥ x).

Giải pháp Heap + Tham lam

Ý tưởng: Mỗi thao tác chọn phần tử lớn nhất để tối ưu điểm. Sử dụng max-heap:

import java.util.PriorityQueue;

class Solution {
    public long maxScore(int[] data, int operations) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        long totalScore = 0;
        
        for (int val : data) maxHeap.offer(val);
        
        while (operations-- > 0) {
            int current = maxHeap.poll();
            totalScore += current;
            maxHeap.offer((current + 2) / 3);
        }
        return totalScore;
    }
}

• Độ phức tạp thời gian: O(n + k log n)
• Độ phức tạp không gian: O(n)

Tối Ưu Bộ Nhớ Bằng Heap Tại Chỗ

Ý tưởng: Biến mảng thành max-heap, duy trì tính chất:

data[i] ≥ max(data[2*i+1], data[2*i+2])

Thực hiện:

1. Heap hóa mảng
2. Lặp k lần: Lấy giá trị đầu heap, cập nhật phần tử này, điều chỉnh heap

class HeapSolution {
    public long maxScore(int[] heapData, int operations) {
        buildMaxHeap(heapData);
        long result = 0;
        
        while (operations-- > 0) {
            result += heapData[0];
            heapData[0] = (heapData[0] + 2) / 3;
            adjustHeap(heapData, 0);
        }
        return result;
    }
    
    void buildMaxHeap(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i);
        }
    }
    
    void adjustHeap(int[] arr, int parent) {
        int size = arr.length;
        while (2 * parent + 1 < size) {
            int child = 2 * parent + 1;
            if (child + 1 < size && arr[child + 1] > arr[child]) {
                child++;
            }
            if (arr[child] <= arr[parent]) break;
            swap(arr, parent, child);
            parent = child;
        }
    }
    
    void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

• Độ phức tạp thời gian: O(n + k log n)
• Độ phức tạp không gian: O(1)