P6002 [USACO20JAN] Berry Picking S 题解

haotian1234 · 2022-05-25 14:53:25 · 题解

题意暗示

• 就是问你如何做到 Bessie 的篮子中所有的浆果数最接近于 Elsie 的篮子中所有的浆果数

  题目分析

  很显然，当 Elsie 的篮子中每一篮的篮子数与 Bessie 的篮子中每一篮的篮子数相等时，答案得到了最优化。

所以我们假设这个值为 min ，既然这时 Elsie 的篮子中每一篮的篮子数与 Bessie 的篮子中每一篮的篮子数有可能不相等，但至少 Elsie 的篮子中每一篮的篮子数要相等，这时，就可以用这个值求出答案。

从数据来看，min 最大也才 1000 ，那我们就枚举 min，不就好了吗。但在枚举时，要分以下几种情况讨论：

假设能装满 min 个浆果的篮子数为 lz。

最后，将每次求出的 Bessie 可以拿到的浆果数进行取最大值，就是答案。

题目坑点

• 一颗浆果树上的浆果可以放入多个篮子
• 但一个篮子不可以放多个浆果树上的浆果

下面就上大家最最最关心的东西——代码：

#include<bits/stdc++.h>
using namespace std;
int n,k,i,a[100100],b[100100],j,ans;
int main(){
    scanf("%d%d",&n,&k);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for (i=a[n];i>=a[1];i--){//枚举
        int lz=0;
        priority_queue<int> q;//优先队列
        for (j=1;j<=n;j++)
            lz+=a[j]/i,q.push(a[j]%i);
        if (lz>k) lz=k;
        if (lz<k/2) continue;
        else{
            int s=(lz-k/2)*i;
            for (j=1;j<=k-lz;j++)
                s+=q.top(),q.pop();
            ans=max(ans,s);//取剩下的
        }
    }
    printf("%d\n",ans);
    return 0;
}