首页 题解 USACO

# [USACO18JAN] Rental Service S

看题意很明显贪心可做，那么咱们就贪心做。

先根据产奶量从高到低给牛排序，有一个很直观的想法就是，如果是卖这个牛所挤出来的牛奶 所赚得的钱还没有 把这头牛卖了赚的钱多，那么咱就把这个牛给卖了，但是考虑一件事就是把他卖了，之后有个产奶量更少的，但正好想要租牛的邻居都已经租完牛了，那么咱只能把之后的那头奶牛拿去挤奶了，很明显这种方法没有咱们现在把这头牛不卖了更优秀～～（蚊子再小也有肉）~~。

把租户所出价格从低到高排序。
当奶牛个数多于租户的数量时，那我们就从 (n−q)(n-q) 开始，然后开始按照上面的方法开始对比，第 ii 头牛，第 jj 个租户，如果是卖牛奶更优，那么答案就加上卖掉第 ii 头牛所赚得的钱，如果是 卖牛更优，那么答案就加上这个租户所能给出的钱，无论怎么样 jj 都得自增 1 （你可以理解成一个租户对应着一头奶牛）。

总结：

  • 只把产量小的卖给邻居，其他的挤奶
  • 把商店给出测价格从大到小排序，只把牛奶卖给出价高得
  • 出给出价高的邻居奶牛，而且只给产奶量低的奶牛。
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <iomanip>
#define int long long
using namespace std;
const int MAXN=1e6+10;
int a[MAXN],c[MAXN];
struct shop{
    int incom,need;
}b[MAXN];
bool cmp(int x,int y){
    return x>y;// 产奶量
}
bool cmp2(shop x,shop y){
    return x.incom>y.incom;// 每家店能给的钱
}
bool cmp3(int x,int y){
    return x<y;
}
signed main(){
    //  freopen("in.in","r",stdin);
    // freopen("out.out","w",stdout);
    int n,m,q;
    cin>>n>>m>>q;             
    for(int i=1;i<=n;i++){
        cin>>a[i];        
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=m;i++){
        cin>>b[i].need>>b[i].incom;
    }
    sort(b+1,b+m+1,cmp2);
    for(int i=1;i<=q;i++){
        cin>>c[i];
    }
    sort(c+1,c+q+1,cmp3);
    int ans=0;
    // 对比一下，把牛卖了还是说卖牛奶赚的多
    if(q>n){// 当想要租牛的人数比有的牛的数量要多，那么就需要看看给的价格
        int nowsale=(q-n)+1;// 从 q-n+1 开始 有个一一对应
        int now=1,ned=b[1].need;
        for(int i=1;i<=n;i++){
            int cpnow=now,cpned=ned;
            int hav=a[i];
            int sum=0;
            while(hav!=0&&cpnow<=m){
                sum+=min(cpned,hav)*b[cpnow].incom;
                if(cpned>hav){
                    cpned-=hav;
                    hav=0;
                }else{
                    hav-=cpned;
                    cpned=b[cpnow+1].need;cpnow++;
                }
            }
//            cout<<i<<" "<<sum<<" "<<c[nowsale]<<endl;
            if(sum<c[nowsale]){
                ans+=c[nowsale];
                nowsale++;
            }else{
                ans+=sum;
                nowsale++;// 这里无论卖不卖牛，都得加一
                now=cpnow,ned=cpned;
            }
        }
    }else{// 如果想要租牛的人数没有比拥有的牛的数量要多，那么就看看产量最少的 q 头牛产生的价值有没有比租出去大
    // 前 (n-q) 头牛肯定是用来当牛奶卖的
        // cout<<"1"<<endl;
        int now=1,ned=b[1].need;
        int nowsale=1;
        for(int i=1;i<=(n-q);i++){// 算出前 (n-q) 头牛可以卖多少钱
            int cpnow=now,cpned=ned;
            int hav=a[i];
            int sum=0;
            while(hav!=0&&cpnow<=m){
                sum+=min(cpned,hav)*b[cpnow].incom;
                if(cpned>hav){
                    cpned-=hav;
                    hav=0;
                }else{
                    hav-=cpned;
                    cpned=b[cpnow+1].need;cpnow++;
                }
            }
            now=cpnow,ned=cpned;
            ans+=sum;
        }
        // cout<<"2"<<" "<<ans<<endl;
        for(int i=(n-q+1);i<=n;i++){
            int cpnow=now,cpned=ned;
            int hav=a[i];
            int sum=0;
            while(hav!=0&&cpnow<=m){
                sum+=min(cpned,hav)*b[cpnow].incom;
                if(cpned>hav){
                    cpned-=hav;
                    hav=0;
                }else{
                    hav-=cpned;
                    cpned=b[cpnow+1].need;cpnow++;
                }
            }
            if(sum<c[nowsale]){
                ans+=c[nowsale];
                nowsale++;
            }else{
                ans+=sum;
                nowsale++;
                now=cpnow,ned=cpned;
            }
        }
    }
    cout<<ans<<endl;
}