logoChat01.ai

class Solution { public: int findMaximizedCapi...

Tạo vào: 30 tháng 5, 2026

Trả lời bằng GPT-5.5 Thinking bởi Chat01

Câu hỏi

class Solution {
public:
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
int n=profits.size();
vector<pair<int,int>> proj;
for(int i=0;i<n;i++){
proj.push_back({capital[i],profits[i]});
}
priority_queue<int> pq;
int idx=0;
int res=0;
while(k--){
while(idx<n){
if(proj[idx].first>w) break;
pq.push(proj[idx].second);
}
if(pq.empty()) return w;
w=w+pq.top();
pq.pop();
// k--;
}
return w;
}
}; fix this

Suy nghĩ

Thought for a couple of seconds

Trả lời

You need to sort projects by required capital and increment idx inside the inner loop. Otherwise, idx never changes and the loop can become infinite.

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

        vector<pair<int, int>> proj;
        for (int i = 0; i < n; i++) {
            proj.push_back({capital[i], profits[i]});
        }

        sort(proj.begin(), proj.end());

        priority_queue<int> pq;
        int idx = 0;

        while (k--) {
            while (idx < n && proj[idx].first <= w) {
                pq.push(proj[idx].second);
                idx++;
            }

            if (pq.empty()) return w;

            w += pq.top();
            pq.pop();
        }

        return w;
    }
};

Main fixes:

cpp
sort(proj.begin(), proj.end());

and inside the inner loop:

cpp
idx++;

Without idx++, the same project keeps getting pushed forever.

Câu hỏi

class Solution {
public:
struct cmp {
bool operator()(pair<int,int>& a, pair<int,int>& b) {
if(a.first == b.first) {
return a.second < b.second;
}
return a.first < b.first;
}
};

text
int lastStoneWeight(vector<int>& stones) {
    unordered_map<int,int> f;
    int n=stones.size();
    priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> pq;
    for(int i=0;i<n;i++){
        f[stones[i]]++;
    }
    for(auto i:f){
        int key =i.first;
        int freq=i.second;
        pair<int,int> curr={key,freq};
        pq.push(curr);
    }
        while(pq.size()>1) {
        if(pq.top().second==1){
            int x=pq.top().first;
            pq.pop();
            if(pq.top().second==1){
                int y=pq.top().first;
                pq.pop();
                pq.push({x-y,1});
            }
            else{
                int z=pq.top().first;
              int c= pq.top().second-1;
              pq.pop();
              pq.push({z,c});
                pq.push({x-z,1});
            }
        }
        else{
            int m=pq.top().first;
           int l= pq.top().second;
           l--;
            if(l==1) pq.pop();
        }
    }
    if(pq.empty()) return 0;
    if(pq.top().second==0)  return 0;
    return pq.top().first;
}

}; fix this

Suy nghĩ

Thought for a couple of seconds

Trả lời

Use a simple max-heap of stone weights. You do not need frequency pairs here.

cpp
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;

        for (int stone : stones) {
            pq.push(stone);
        }

        while (pq.size() > 1) {
            int x = pq.top();
            pq.pop();

            int y = pq.top();
            pq.pop();

            if (x != y) {
                pq.push(x - y);
            }
        }

        return pq.empty() ? 0 : pq.top();
    }
};

Why your code was breaking:

cpp
pq.push({x - y, 1});

can push 0, which should not be added.

Also here:

cpp
else {
    int m = pq.top().first;
    int l = pq.top().second;
    l--;
    if(l==1) pq.pop();
}

you reduce l, but you never update the heap with the new frequency. Also, when two equal stones are smashed, the frequency should decrease by 2, not 1.

The heap-only solution is the cleanest and accepted approach.

Chia sẻ Q&A này