logoChat01.ai

class Solution { public: int findMaximizedCapi...

创建于：2026年5月30日

使用 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.

分享这个问答