P6002 [USACO20JAN] Berry Picking S 题解

_szs9601 · 2022-05-30 14:36:11 · 题解

思路

假设 Elsie 拿的篮子里面果子数最小值为 m，那么最好情况是她拿的篮子里全都是 m 个果子。所以我们直接暴力枚举这个 m，然后就能在剩下的果子中选择最多的那几组果子，就可以求出 Bessie 能得到的最多的果子数了。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,s,ans,k,a[100100];
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(i=a[n];i>=a[1];i--){//枚举m
        s=0;
        priority_queue<int>q;//有限队列，大顶堆
        for(j=1;j<=n;j++) s+=a[j]/i,q.push(a[j]%i);//求出装满若干篮子之后剩余的果子数
        if(s>=m){ans=max(ans,i*m/2);continue;}//说明两人都能取到i*m/2的果子数
        if(s<m/2) continue;//不满足最小条件
        k=m-s;s=(s-m/2)*i;
        for(j=1;j<=k;j++) s+=q.top(),q.pop();
        ans=max(ans,s);//让Bessie得到最多的果子
    }
    printf("%d\n",ans);
    return 0;
}