自动搬运

查看原文

来自洛谷，原作者为

	ZTengW ユユ症患者||☆ super マサラダ dance time ☆||资瓷壶关||未关私||性别奇美拉||潜水员||社交恐怖分子

搬运于2025-08-24 21:57:24，当前版本为作者最后更新于2025-08-18 21:53:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

解法

我一开始尝试的是从大到小枚举留下的奶牛的个数，但是没写出来（感兴趣的可以自己去尝试着写一下）。
正所谓正难则反，所以我决定从小到大枚举个数。
也就是 $i$ 从 $0$ 开始到 $n$，然后去计算所用的总钱数，再求出其中的最大值就可以了。
由于是从小到大枚举个数，所以买牛奶所得的钱数只增不减，记录牛奶总量的变量和记录总钱数的变量就不用在循环里面设置初始值。
当然，题目也告诉我们了，一定要开 long long。

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll c[100005],rnd[100005];
struct node
{
    ll p,q;
}sld[100005];
bool rcmp(ll x,ll y)
{
    return x>y;
}
bool scmp(node x,node y)
{
    return x.p>y.p;
}
int main()
{
    ll n,m,r,ans=0,sum=0,milk=0;
    scanf("%lld%lld%lld",&n,&m,&r);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&c[i]);
    for(ll i=1;i<=m;i++)
        scanf("%lld%lld",&sld[i].q,&sld[i].p);
    for(ll i=1;i<=r;i++)
        scanf("%lld",&rnd[i]);
    sort(c+1,c+1+n,rcmp);
    sort(rnd+1,rnd+1+r,rcmp);
    sort(sld+1,sld+1+m,scmp);
    for(ll i=1;i<=r;i++)
        rnd[i]+=rnd[i-1];
    ll cur=1;
    for(ll i=0;i<=n;i++)
    {
        milk+=c[i];
        while(cur<=m&&milk>=sld[cur].q)
        {
            sum+=sld[cur].q*sld[cur].p;
            milk-=sld[cur].q;
            cur++;
        }
        if(cur<=m)
        {
            sum+=sld[cur].p*milk;
            sld[cur].q-=milk;
            milk=0;
        }
        sum+=rnd[min(n-i,r)];
        ans=max(ans,sum);
        sum-=rnd[min(n-i,r)];
    }
    printf("%lld",ans);
    return 0;
}

一些细节

不要问我为什么代码放完了才讲

• while 循环结束后可能会出现还有牛奶没卖的情况，所以仍要进行判断。
• 尽管卖牛奶所得的钱只增不减，但是租奶牛所得的钱仍然要回溯。