USACO 2020 January Contest, Silver Problem 1. Berry Picking

USACO 2020 January Contest, Silver Problem 1. Berry Picking

Bessie and her little sister Elsie are picking berries in Farmer John's berry patch. Farmer John's patch has exactly?NN?berry trees (1≤N≤10001≤N≤1000); tree?ii?contains exactly?BiBi?berries (1≤Bi≤10001≤Bi≤1000). Bessie has exactly?KK?baskets (1≤K≤10001≤K≤1000,?KK?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/2K/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.

 

 

 

 

SAMPLE INPUT:

5 4
3 6 8 4 2

SAMPLE OUTPUT:

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.

 

Problem credits: Nathan Pinsker

<h3>USACO 2020 January Contest, Silver Problem 1. Berry Picking? 题解(翰林国际教育提供，仅供参考)</h3>
<p style="text-align: center;">题解请<a href="/register" target="_blank" rel="noopener">注册</a>或<a href="/login" target="_blank" rel="noopener">登录</a>查看</p>
[/hide]

(Analysis by Dhruv Rohatgi, Benjamin Qi)

Small?KK:

After sorting the trees in decreasing order of?BiBi, we don't need to consider trees outside of the first?K.K.?Furthermore, if we decide to select?b>0b>0?baskets from tree?i,i,?then each basket should have either??Bib??Bib??or??Bib?+1?Bib?+1?berries. Using these observations, we can do some sort of backtracking.

Full Solution:

Let?bb?the minimum number of berries in one of the buckets that Elsie receives. Without loss of generality, we can assume that all of Elsie's buckets contain exactly?bb?berries. Now our goal is to maximize the number of berries placed into?KK?buckets of size at most?bb?such that at least?K2K2?buckets have exactly?bb?berries inside.

Consider a single tree's allotment into the buckets in an optimal solution. There's no point having multiple buckets with less than?bb?berries from this tree. So all buckets will have exactly?bb?berries aside from at most one.

Thus, it's clearly optimal to repeatedly fill buckets of size exactly?bb?until we run out of buckets or all trees have less than?bb?berries remaining. If we still have buckets to fill, sort the remaining trees by?Bi(modb)Bi(modb)?and iterate from the largest to the smallest value.

We can repeat this procedure for each?b=0…max(Bi),b=0…max(Bi),?which runs in?O(max(Bi)?NlogN)O(max(Bi)?Nlog?N)?time.

Dhruv Rohatgi's code:

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int N,K;
int A[100000];
int mod;
 
bool cmp(int a,int b)
{
	return (a%mod) > (b%mod);
}
 
int main()
{
	freopen("berries.in","r",stdin);
	freopen("berries.out","w",stdout);
	cin >> N >> K;
	int M = 0;
	for(int i=0;i<N;i++)
	{
		cin >> A[i];
		M = max(M, A[i]);
	}
	int best = 0;
	for(int b=1;b <= M;b++)
	{
		int full = 0;
		for(int i=0;i<N;i++)
			full += A[i]/b;
		if(full < K/2)
			break;
		if(full >= K)
		{
			best = max(best, b*(K/2));
			continue;
		}
		mod = b;
		sort(A, A+N, cmp);
		int cur = b*(full - K/2);
		for(int i=0;i<N && i+full<K;i++)
			cur += A[i]%b;
		best = max(best,cur);
	}
	cout << best << '\n';
}

[/hide]