Priority Queue

Priority-Queue

最后一块石头的重量

class Solution {
public:
	int lastStoneWeight(vector<int>& stones) {
		priority_queue<int> q;
		for(auto v:stones){
			q.push(v);
		}
		while(q.size()>1){
			int x=q.top();
			q.pop();
			int y=q.top();
			q.pop();
			if(x!=y)
				q.push(x-y);
		}
		if(q.size()==0)
			return 0;
		int ans=q.top();
		return ans;
	}
};

从数量最多的堆取走礼物

class Solution {
public:
	long long pickGifts(vector<int>& gifts, int k) {
		priority_queue<long long > q;
		for(auto v:gifts){
			q.push(v);
		}
		while(k--){
			long long top=q.top();
			q.pop();
			top=int(sqrt(top));
			q.push(top);
		}
		long long ans=0;
		while(q.size()!=0){
			ans+=q.top();
			q.pop();
		}
		return ans;
	}
};

##

BackLink