Daily 15/06/2024: [502. IPO](https://leetcode.com/problems/continuous-subarray-sum/)

# 1. Tóm tắt đề bài

Giả sử LeetCode sẽ sớm bắt đầu IPO. Để bán được giá cổ phiếu tốt cho Venture Capital, LeetCode mong muốn thực hiện một số dự án nhằm tăng vốn trước đợt IPO . Vì nguồn lực hạn chế nên nó chỉ có thể hoàn thành hầu hết kcác dự án riêng biệt trước khi IPO . Giúp LeetCode thiết kế cách tốt nhất để tối đa hóa tổng vốn sau khi hoàn thành ở hầu hết kcác dự án khác nhau.

Bạn được giao ```n``` dự án mà dự án thứ ```i``` có lợi nhuận thuần túy ```profits[i]``` và cần có số vốn tối thiểu ```capital[i]``` để bắt đầu dự án. Ban đầu bạn có ```w``` vốn. Khi bạn hoàn thành một dự án, bạn sẽ thu được lợi nhuận thuần túy của nó và lợi nhuận sẽ được cộng vào tổng vốn của bạn.

Chọn danh sách tối đa ```k``` các dự án khác biệt với các dự án nhất định để tối đa hóa số vốn cuối cùng của bạn và hoàn lại số **vốn tối đa cuối cùng **.

Câu trả lời được đảm bảo phù hợp với số nguyên có trong khoảng 32 bit.

#### Giới hạn
- $1 \le$ ```k``` $\le 10^5$
- $1 \le$ ```n``` $\le 10^5$
- $0 \le$ ```w``` $\le 10^9$
- $0 \le$ ```profits[i]``` $\le 10^4$
- $1 \le$ ```capital[i]``` $\le 10^9$

# 2. Tóm tắt lời giải
#### Phân tích
- Nếu mọi người chú ý làm các bài Daily trong tuần này thì đều sử dụng tham lam. Bài hôm nay cũng không ngoại lệ.
- Trước hết thì mọi người phải hiểu được đề bài, tức là khi chúng ta có vốn w thì sau khi thực hiện một dự án thứ i chẳng hạn thì vốn của chúng ta sẽ thành ```w + profits[i]``` nhưng mà ```w >= capital[i]``` thì mới được thực hiện dự án. Như vậy mọi người có thể nghĩ ngay tới chiến lược chọn ra thằng nhiều lợi ích nhất trong khả năng có thể, sau đó khi vốn tăng tiếp cận nhiều dự án hơn, lại chọn tiếp thằng lợi ích nhiều nhất. Cứ như vậy thì vốn sẽ đạt lợi ích tối đa.

- Thế thì chúng ta sẽ thực hiện triển khai thuật toán như nào?
- Trước hết là chạy trâu đi, chúng ta có một vòng từ ``0`` tới ```k```, mỗi vòng sẽ chọn dự án có lợi ích lớn nhất. Và tất nhiên lớn nhất với số vốn hiện tại, chúng ta sẽ phải for một lượt để xem dự án nào với số vốn hiện tại có thể làm (Nhớ là làm rồi thì không xét tới) rồi tìm dự án "ngon" nhất. Độ phức tạp là $O(n^2)$. Tất nhiên là không qua bài này rồi.
- Để cái tiến dần thì chúng ta sẽ sử dụng Max Heap. Cây Max Heap giống như một Queue hoặc Stack nhưng nó không trả về đầu hoặc cuối mà nó trả về phần tử có giá trị lớn nhất. Như vậy mỗi khi chúng ta tăng vốn thì thêm những dự án có thể tiếp cận vào và "Bùm" cây Max Heap trả về dự án "ngon nhất" trong ```O(1)```.
- Tuy nhiên đọc đến đây, thì bạn đọc có thể thắc mắc mỗi lần thêm những dự án có thể tiếp cận vào thì vẫn mất $O(n)$. Thế nếu nhưng dự án đã được xắp xếp sẵn theo mức vốn điều kiện thì sao ? Cả quá trình chúng ta chỉ mất $O(n)$ chứ không phải từng bước mất $O(n)$ nữa. Bằng cách chúng ta sẽ có một vị trí ```j``` kiểm soát là vốn đạt được tới dự án nào rồi.

Lưu ý: Cấu trúc Max Heap trong các ngôn ngữ là khác nhau. VD: ```C++, C#``` là ```priority_queue, PrirotyQueue```, ```Python``` là ```heapq```.

# 3. Lời giải chi tiết
#### Thuật toán
- Chúng ta phải xắp xếp lại dự án theo Capitals. Sau đó triển khai như trong phần phân tích.

#### Code
- C#

public class Solution {
    public int FindMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.Length;

        var projects = new List<(int capital, int profit)>();

        for (var i = 0; i < n; i++) projects.Add((capital[i], profits[i]));

        projects = projects.OrderBy(x => x.capital).ToList();
        var pq = new PriorityQueue<int, int>();

        var j = 0;
        for (var i = 0; i < k; i++) {
            while (j < n && projects[j].capital <= w) {
                pq.Enqueue(projects[j].profit, int.MaxValue - projects[j].profit);
                j++;
            }

            if (pq.Count == 0) break;
            w += pq.Dequeue();
        }

        return w;
    }
}

- C++

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();
        vector<pair<int,int> > projects;

        for (int i = 0 ; i < n ; i++) projects.emplace_back(capital[i], profits[i]);
        sort(projects.begin(), projects.end());

        priority_queue<int> pq;

        int result = w;
        int j = 0;
        for (int i = 0 ; i < k ; i++) {
            while (j < n and projects[j].first <= result) {
                pq.push(projects[j].second);
                j++;
            }
            if (pq.empty()) break;
            result += pq.top();
            pq.pop();
        }

        return result;
        
    }
};

#### Độ phức tạp
$O(nlog(n))$.
# 4. Kết luận & gợi ý mở rộng
- Một bài cuối tuần không nhẹ nhàng lắm.

> Hãy dùng nghị lực và sự kiên trì để đánh bại mọi thứ.

###### #Hashtag: <span style='color: blue'>Max Heap, Prority Queue</span>