【每日一题】Supermarket

Supermarket

题目大意：

超市有n种商品，每个商品都有一个利润和保质期，超市每天只可以卖一种商品，求超市在保质期内卖出商品可获得的最大利益。

思路：
贪心+二叉堆优化
在最大的保质期时间内找出利润最大的商品卖掉，这个贪心思路是正确的，我们会发现我们的每一个选择都会被商品的保质期影响，即我们必须在商品的保质期内卖出商品，所以我们可以将保质期与可选择的次数相结合，得到以下方法：
将每种商品的保质期按从小到大顺序排序。
使用小根堆维护已经选择商品的价值，然后继续选择商品，这时会有这两种情况：
1.当前商品的保质期大于已经选择商品的次数，直接将此商品加入选择之中；
2.当前商品的保质期等于已经选择商品的次数，将这个商品的价值与小根堆的堆顶作比较，如果大于即替换，否则不变。
因为每次都选择最优的选项，保证了算法的正确性。
代码：

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e4+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[8][2]={-1,0,1,0,0,-1,0,1,1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}

int p[N],t[N],c[N];
bool cmp(int x,int y){return t[x]<t[y];}
void solve(){
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++)cin>>p[i]>>t[i];
        for(int i=1;i<=n;i++)c[i]=i;
        sort(c+1,c+n,cmp);
        priority_queue<int,vector<int>,greater<int>>q;
        int sum=0;
        for(int i=1;i<=n;i++){
            int x=c[i];
            if(t[x]>q.size())q.push(p[x]),sum+=p[x];
            else {
                if(q.top()<p[x])sum+=p[x]-q.top(),q.pop(),q.push(p[x]);
            }
        }
        cout<<sum<<endl;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}