题解：P4181 [USACO18JAN] Rental Service S

· · 题解

题目传送门

解法

我一开始尝试的是从大到小枚举留下的奶牛的个数，但是没写出来（感兴趣的可以自己去尝试着写一下）。
正所谓正难则反，所以我决定从小到大枚举个数。
也就是 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;
}

一些细节

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