Berry Picking（思维）

题目描述
Bessie and her little sister Elsie are picking berries in Farmer John’s berry patch. Farmer John’s patch has exactly N berry trees (1≤N≤1000); tree i contains exactly Bi berries (1≤Bi≤1000). Bessie has exactly K baskets (1≤K≤1000, K even). Each basket can hold as many berries from a single tree as Bessie wants, but cannot contain berries from two different trees as their flavors will clash with each other. Baskets may remain empty.
Bessie wants to maximize the number of berries she collects. However, Farmer John wants Bessie to share with her little sister, and so Bessie will have to give Elsie the K/2 baskets with the largest number of berries. This means that Elsie may even end up with more berries than Bessie, which is very unfair, but unfortunately, sibling dynamics are not always fair.

Help Bessie figure out the maximum number of berries she can collect.

输入
The first line of input contains space-separated integers N and K.
The second line contains N space-separated integers B1,B2,…,BN.

输出
A single line with the answer.

样例输入
5 4
3 6 8 4 2

样例输出
8

提示
If Bessie fills
·one basket with 6 berries from tree 2
·two baskets, each with 4 berries from tree 3
·one basket with 4 berries from tree 4
then she receives two baskets each with 4 berries, giving her 8 berries in total.

思路
对于每种取法，其都具有一个基础值x，且x在[1,maxb]之间，枚举区间内的每一个x，即可得到其能取到的所有桶数temp，若temp<k/2，那么Bessie能拿到的个数恒等于0，那么就不需要对之后的值进行遍历，若temp>k/2 且 temp<k，这个区间内的值为所取得的(temp-k/2)*x+能用剩下的桶装下的剩余的果子，当temp>=k时，能拿到的个数为x*(k/2)

代码实现

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=100005;
const int M=35;
const int INF=0x3f3f3f;
const ull sed=31;
const ll mod=1e9+7;
const double eps=1e-8;
typedef pair<int,int>P;
typedef pair<double,double>Pd;

int n,k,bmod,ans,maxb;
int b[N];

bool cmp(int a,int b)
{
    return (a%bmod)>(b%bmod);
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
        maxb=max(maxb,b[i]);
    }
    for(int i=1;i<=maxb;i++)
    {
        int temp=0;
        for(int j=0;j<n;j++) temp+=b[j]/i;
        if(temp<k/2) break;
        if(temp>=k)
        {
            ans=max(ans,i*(k/2));
            continue;
        }
        bmod=i;
        sort(b,b+n,cmp);
        int t=i*(temp-k/2);
        for(int j=0;j<n && j+temp<k;j++) t+=(b[j]%bmod);
        ans=max(ans,t);
    }
    printf("%d\n",ans);
    return 0;
}