logoChat01.ai

class Solution { public: int findMaximizedCapi...

Создано: 30 мая 2026 г.

Отвечено с использованием GPT-5.5 Thinking от Chat01

Вопрос

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

Мысль

Thought for a couple of seconds

Ответ

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.

Вопрос

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

Мысль

Thought for a couple of seconds

Ответ

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.

Поделиться этим Q&A