USACO 2020 January Contest, Silver

1.Berry Picking

题目意思

给定 \(n\) 颗树，分别有 \(a_i\) 个果子，求选出 \(m\) 篮果子使得最少的 \(\frac{m}{2}\) 篮最多，要求每篮的果子都必须来自同一棵树。

思路

1. 我们要先知道，要使最少的 \(\frac{m}{2}\) 篮果子多一些，就是要使得最多的 \(\frac{m}{2}\) 篮果子少一些，而我们要让人果子取值更灵活，所以我们第 \(\frac{m}{2}\) 个果篮要尽量多，由此我们可以得到最多的 \(\frac{m}{2}\) 篮子果子的数量要相同。
2. 然后再枚举果子的个数 \(w\)，把取出来的果子的篮子为整篮，然后我们用贪心算法，设出 \(now\) 表示最多取出的整篮数。

情况分为以下：

1. \(now ≥ m\) ，答案为 \(\frac{m}{2}×w\) 。
2. \(now≥\frac{m}{2}\) 答案就为 \((now-\frac{m}{2}×w)\)
3. \(now≤\frac{m}{2}\) 无答案

#include <bits/stdc++.h>
using namespace std;
const int N = 1500;
int n, k, maxx = 0, res = 0;
int a[N];
int main()
{
    freopen("berries.in", "r", stdin);
    freopen("berries.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        maxx = max(maxx, a[i]);
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= maxx; i++)
    {
        priority_queue<int> q;
        int ans = 0;
        for (int j = 1; j <= n; j++)
            ans += a[j] / i, q.push(a[j] % i);
        if (ans < k >> 1)
            continue;
        else if (ans < k)
        {
            int t = ans - (k >> 1), cr = t * i;
            t = (k >> 1) - t;
            while (t--)
                cr += q.top(), q.pop();
            res = max(res, cr);
        }
        else
            res = max(res, (k >> 1) * i);
    }
    cout << res << endl;
    return 0;
}