Bessie 和她的妹妹 Elsie 正在农夫约翰的浆果园里采浆果。
农夫约翰的浆果园里有 N 棵浆果树;树 i 上有 Bi 个浆果。
Bessie 有 K 个篮子。
每个篮子里可以装同一棵树上采下的任意多个浆果,但是不能装来自于不同的树上的浆果,因为它们的口味可能不同。
篮子里也可以不装浆果。
Bessie 想要使得她得到的浆果数量最大。
但是,农夫约翰希望 Bessie 与她的妹妹一同分享,所以 Bessie 必须将浆果数量较多的 K2 个篮子给 Elsie。
这表示 Elsie 很有可能最后比 Bessie 得到更多的浆果,这十分不公平,然而姐妹之间往往就是这样。
帮助 Bessie 求出她最多可以得到的浆果数量。
输入格式
输入的第一行包含空格分隔的整数 N 和 K。
第二行包含 N 个空格分隔的整数 B1,B2,…,BN。
输出格式
输出一行,包含所求的答案。
数据范围
1≤N≤1000,
1≤Bi≤1000,
1≤K≤1000, K为偶数。
输入样例:
5 4
3 6 8 4 2
输出样例:
8
样例解释
如果 Bessie 在
一个篮子里装树 2 的 6 个浆果
两个篮子里每个装树 3 的 4 个浆果
一个篮子里装树 4 的 4 个浆果
那么她能够得到两个各装有 4 个浆果的篮子,总共 8 个浆果。
算法
(暴力枚举) $O(BNlogN)$
从小到大枚举Bessie的k/2个篮子里面最多的篮子里面的苹果数目,统计一共可以装多少个篮子,如果可以装的篮子个数小于k/2,那么结束,否则计算除去k/2个篮子以后,剩余的k/2个篮子最多可以装多少,因为是计算最多可以装多少,所以我们需要将苹果的数目从大到小排序(由于已经去除了装满篮子的苹果数目,所以我们只需要对每棵苹果数对i取余的结果进行排序,然后依次选取即可)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int a[N];
int i;
bool cmp(int x,int y)
{
return x%i>y%i;
}
int main()
{
int n,k;
cin>>n>>k;
int s=0;
for(int i=1;i<=n;i++) cin>>a[i];
for(i=1;;i++) //枚举可能可以的答案
{
int t=0;
for(int j=1;j<=n;j++) //计算i个苹果一篮,一共可以装多少篮
{
t+=a[j]/i;
}
if(t<k/2)//如果不够k/2则结束
{
break;
}
int r=min(k/2,t-k/2); //计算给了Elsie 以后还剩下的完整的篮子的数目
int v=r*i; //计算Bessie 中装满篮子的苹果的数目
sort(a+1,a+n+1,cmp); //取余从大到小排序
for(int j=1;j<=min(n,k/2-r);j++) //取最多的j个篮子里面的苹果数目
{
v+=a[j]%i;
}
s=max(s,v); //更新最大值
}
cout<<s;
return 0;
}