145. 超市【小根堆 贪心】

将商品按照时间从小到大排序。如果说此时物品的时间小于堆内的数量。说明堆内有几个物品是要过期的。
那么我们用小根堆来维护，直接取最小的删除即可。

#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; int n; int main(void) {while(cin>>n){vector<PII>ve;for(int i=0;i<n;i++){int price,t; cin>>price>>t;ve.push_back({t,price});}sort(ve.begin(),ve.end());//按照时间从小到大排序priority_queue<int,vector<int>,greater<int>>heap;for(int i=0;i<ve.size();i++){heap.push(ve[i].second);if(heap.size()>ve[i].first) heap.pop();//堆内的元素个数,大于最晚卖的时间，将最小价值的物品弹出}int sum=0;while(heap.size()) sum+=heap.top(),heap.pop();cout<<sum<<endl;}return 0; }

总结

以上是生活随笔为你收集整理的145. 超市【小根堆 贪心】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。