P3045 题解

· · 题解

蒟蒻的第一篇题解

>> P3045 [USACO12FEB]Cow Coupons G

题目分析

读完题目，我们不难发现这是一道贪心题。接下来我们考虑贪心策略。

不难发现答案组成要么全部使用优惠券，要么一部分使用优惠券，一部分不使用优惠券。

因此，我们可以考虑先对 C_i 进行排序，前 k 只奶牛都使用优惠券，定义 cnt 为可购买的奶牛数。此时，若 C_i 的前 j ( j \le k ) 项之和大于 m ，则可证明答案即为 j - 1 ，下面给出简单证明：

由于 \begin{cases} \sum_{ i = 1 }^j C_i > m \\ \sum_{ i = 1 }^{ j - 1 } C_i \le m \end{cases} ，且对于任意 C_i 有 C_i \le P_i ，则对于任意 P_i ( i \ge j ) 有 P_i \ge C_j ，所以不可能在总钱数不超过 m 的情况下购买更多的奶牛。这是第一种情况。

接下来分析第二种情况，此时一定有 cnt > k ，对于答案中不使用优惠券的部分，容易得到有以下两种取法：

  1. 从第 k+1 到第 n 只奶牛中选取一只 P 值最小的奶牛 w ，此时总钱数的增加量为 P_w 。

  2. 从前 k 只奶牛中选取一只 P 值与 C 之差最小的奶牛 a ，再从第 k+1 到第 n 只奶牛中选取一只 C 值最小的奶牛 b ，并将 a 的优惠券给 b 使用，此时总钱数的增加量为 P_a - C_a + C_b 。

根据贪心的思想，我们应该使每次更新答案时总钱数的增加量尽可能的小，这样才能购买到尽可能多的奶牛，即总钱数的增加量应为 \min ( P_w , P_a - C_a + C_b ) 。最后对于第 k+1 到第 n 只奶牛更新一次答案，就可以得到最终的答案。

代码实现

可以开一个结构体数组存每只奶牛的 P 值和 C 值，然后以每只奶牛的 C 值作为第一关键字给这个数组排序。对于第一种情况，遍历一遍前 k 只奶牛，若过程中总钱数超过 m ，则直接输出答案。对于第二种情况，可以开三个优先队列，分别存：

  1. 前 k 只奶牛的 P 值与 C 值之差。

  2. 第 k + 1 到第 n 只奶牛的 C 值。

  3. 第 k + 1 到第 n 只奶牛的 P 值。

然后遍历一遍第 k + 1 到第 n 只奶牛更新答案。若第一种取法更优，则将总钱数增加 P_w ，并弹出前两个队列的队首元素；反之，将总钱数增加 P_a - C_a + C_b ，并弹出第三个队列的队首元素。此时有两种特殊情况需要注意：

  1. 第一个队列在某一时刻可能为空，此时不能使用第二种取法更新答案。

  2. 第二个队列的队首元素与第三个队列的队首元素可能属于同一只奶牛，由于每只奶牛只能购买一次，所以更新答案时要同时弹出三个队列的队首元素。

下面给出代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
typedef pair<int,int> paii;
priority_queue<paii,vector<paii>,greater<paii>> q1,q2,q3;
struct Cow{
    int p;
    int c;
};
Cow cow[N];
bool vst[N];
bool cmp(Cow a,Cow b)
{
    return a.c<b.c;
}
int main(){
    int n,k;
    long long m;
    cin>>n>>k>>m;
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&cow[i].p,&cow[i].c);
    }
    sort(cow+1,cow+n+1,cmp);
    long long tot=0;
    for(int i=1;i<=k;++i)
    {
        tot+=cow[i].c;
        q1.push(make_pair(cow[i].p-cow[i].c,i));
        if(tot>m)
        {
            printf("%d",i-1);
            return 0;
        }
    }
    for(int i=k+1;i<=n;++i)
    {
        q2.push(make_pair(cow[i].c,i));
        q3.push(make_pair(cow[i].p,i));
    }
    for(int i=k+1;i<=n;++i)
    {
        int k1=q2.top().second,k2=q3.top().second;
        int v1,v2=q3.top().first;
        if(!q1.empty())
        {
            v1=q2.top().first+q1.top().first;
            tot+=min(v1,v2);
        }
        else
        {
            tot+=v2;
        }
        if(tot<=m)
        {
            if(q1.empty())
            {
                if(k1==k2)
                {
                    q2.pop();
                }
                q3.pop();
            }
            else
            {
                if(v1>=v2)
                {
                    if(k1==k2)
                    {
                        q2.pop();
                    }
                    q3.pop();
                }
                else
                {
                    if(k1==k2)
                    {
                        q3.pop();
                    }
                    q1.pop(),q2.pop();
                }
            }   
        }
        else
        {
            printf("%d",i-1);
            return 0;
        }
    }
    printf("%d",n);
    return 0;
}