Supermarket（贪心）

ruoye123456 / 2024-09-18 / 原文

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> PII;
void solve()
{
    int n;
    while(cin>>n)
    {
        vector<PII> a(n);
        for(int i=0;i<n;++i) cin>>a[i].y>>a[i].x;
        sort(a.begin(),a.end());
        //对于前t天选择可以选择的最大t个物品
        //建立小根堆，若当前物品的过期日期<=t则判断是否更换堆顶
        //否则直接插入堆
        priority_queue<int,vector<int>,greater<int>> q;
        //t表示已经考虑完了多少天
        int t = 0;
        for(int i=0;i<n;++i)
        {
            if(a[i].x == t)
            {
                if(a[i].y > q.top()) 
                {
                    //cout<<"1. "<<a[i].y<<' '<<q.top()<<'\n';
                    q.pop();
                    q.push(a[i].y);
                }
            }
            else if(a[i].x > t) 
            {
                //cout<<"2. "<<a[i].y<<'\n';
                q.push(a[i].y), t++;
            }
        }
        ll res = 0;
        while(!q.empty())
        {
            res += q.top();
            //cout<<"res "<<q.top()<<'\n';
            q.pop();
        }
        cout<<res<<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
}