2416. Berry Picking

2416. Berry Picking

题目描述

Bessie 和她的妹妹 Elsie 正在 Farmer John 的浆果园里采浆果。Farmer John 的浆果园里有 N 棵浆果树（1≤N≤1000）；树 i 上有 Bi 个浆果（1≤Bi≤1000）。Bessie 有 K 个篮子（1≤K≤1000，K 为偶数）。每个篮子里可以装同一棵树上采下的任意多个浆果，但是不能装来自于不同的树上的浆果，因为它们的口味可能不同。篮子里也可以不装浆果。
Bessie 想要使得她得到的浆果数量最大。但是，Farmer John 希望 Bessie 与她的妹妹一同分享，所以 Bessie 必须将浆果数量较多的 K/2 个篮子给 Elsie。这表示 Elsie 很有可能最后比 Bessie 得到更多的浆果，这十分不公平，然而姐妹之间往往就是这样。
帮助 Bessie 求出她最多可以得到的浆果数量。

输入

输入的第一行包含空格分隔的整数 N 和 K。
第二行包含 N 个空格分隔的整数 B1,B2,…,BN。

输出

输出一行，包含所求的答案。

样例输入

5 4
3 6 8 4 2

样例输出

8

数据范围限制

测试点 1-3 满足 K≤10。
测试点 4-10 没有额外限制。

提示

如果 Bessie 在一个篮子里装树 2 的 6 个浆果
两个篮子里每个装树 3 的 4 个浆果
一个篮子里装树 4 的 4 个浆果
那么她能够得到两个各装有 4 个浆果的篮子，总共 8 个浆果。

题目思路：
Bessie取到的总浆果数在最好的情况下，最多为m*(k/2) （m表示妹妹取到最小那一篮数量（理论上m可以从1到maxn））。
于是，我们假设每棵树上都取i（i=1~maxn)颗浆果，最多可以得到lz篮浆果。（每篮都是i颗）。分三种情况讨论：

1. 如果lz<（k/2） 她就每篮不会取那么多颗浆果（i变小，她得到的会更多，慢慢想，你会明白的）
2. 如果 lz>=k,这个最好理解，这是最好情况，Bessie将获得i*(k/2)颗浆果；
3. （k/2)<lz<k,这种情况，Bessie会先取lz-(k/2)篮，再会尽量取与i接近的篮子，直至取够为止；
   注意：我们枚举i,满足条件的解不一定就是最优解，需要打擂台，你懂的；

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std;
const int MAX=2147483647;
const int N=1e3+5;
int n,k,maxn,ans,mod,f[N];
bool cmp(int x, int y) {return x%mod>y%mod;}
void input()
{
	cin>>n>>k;
	for (int i=1;i<=n;i++) 
	{
        cin>>f[i];
        maxn=max(maxn,f[i]);
    }
}
void work()
{
	for (int i=1;i<=maxn;i++)
	{
    	int lz=0;         //lz表示每篮最少放i个浆果,最多可以装多少篮； 
    	for (int j=1;j<=n;j++)
        	lz+=f[j]/i;
        if(lz<(k/2))   break;
        if(lz>=k) 
		{
            ans=max(ans,i*(k/2));
            continue;
    	}
		//(k/2)<lz<k的情况，先取(lz-(k/2))*i，然后对每棵树按取模i的情况降序排序;
		//按顺序取够剩下的篮数（贪心：每篮都是不够i颗浆果的，但最接近i颗的篮子优先取;) 
		mod=i;
        sort(f+1,f+n+1,cmp);
        int temp=(lz-(k/2))*i;
        for(int j=1;j<=n&&j+lz<=k;j++)
            temp+=f[j]%i;  //注意这里是顺序取每棵树取模剩下最多浆果的那一篮，取够为止； 
        ans=max(ans,temp); 
	}
}
int main()
{
	//fre(berries);
	input();
    work();
    cout<<ans;
	return 0;
}