题解 P3045 【[USACO12FEB]牛券Cow Coupons】

justin_cao · 2018-11-07 19:23:27 · 题解

这道题目首先我们可以考虑贪心，我们先把c值最小的k个元素的c值之和变成答案，因为这个肯定是在答案里的。然后我们考虑怎么去往后面加元素，我们考虑维护三个优先队列，一个维护c值，一个维护p值的小根堆，一个维护用了优惠券的p和c的差，也就是优惠的钱的小根堆。然后我们考虑先把后面n-k个元素都打进去，然后我们考虑怎么取得下一个元素使得花费最少。

我们首先考虑取维护c值的小根堆，这个如果要用就代表着这个要替换那k个用了优惠券的，那么通过贪心的思路可以想到肯定是取优惠最少的进行替换，那么如果将这两个替换的花费就为：c值最小的+p和c的差值最小的。也就是说，我们不仅需要买这个东西，我们还需要补上这个东西替换的那个东西的差价。

然后我们考虑取维护p值的小根堆，这个非常显然就是p值最小的那一个作为花费。

那么我们比较两种取值的花费，那个小就取哪个即可。

下面是代码，结合代码可能比较好理解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 50010
using namespace std;
typedef long long ll;
ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct P{
    int p,c;
}a[maxn];
int n,k;
ll m;
bool cmp(P x,P y)
{
    return x.c<y.c;
}
priority_queue<int,vector<int>,greater<int> >q1;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q2,q3;
int book[maxn];
int main()
{
    n=read();k=read();m=read();
    for(int i=1;i<=n;i++)
    {
        a[i].p=read();
        a[i].c=read();
    }
    sort(a+1,a+n+1,cmp);
    ll now=0;
    for(int i=1;i<=k;i++)
    {
        now+=a[i].c;
        if(now>m)
        {
            printf("%d\n",i-1);
            return 0;
        }
        q1.push(a[i].p-a[i].c);
    }
    if(k==n)
    {
        printf("%d\n",n);
        return 0;
    }
    for(int i=k+1;i<=n;i++)
    {
        q2.push(make_pair(a[i].c,i));
        q3.push(make_pair(a[i].p,i));
    }
    int ans=k;
    for(int i=k+1;i<=n;i++)
    {
        while(book[q2.top().second])  q2.pop();
        while(book[q3.top().second])  q3.pop();
        int p1=q2.top().second;
        int p2=q3.top().second;
        int tmp1=q2.top().first+q1.top();
        int tmp2=q3.top().first;
        if(tmp1<tmp2)
        {
            now+=tmp1;
            q1.pop();q2.pop();
            q1.push(a[p1].p-a[p1].c);
            book[p1]=1;
        }
        else{
            now+=tmp2;
            q3.pop();
            book[p2]=1;
        }
        ans++;
        if(now>m)
        {
            printf("%d\n",ans-1);
            return 0;
        }
    }
    printf("%d\n",n);
    return 0;
}