$$\Large \href {/blog/content/29450/} {\color {Lime} {\text {USACO 2022 十二月月赛铜组 && 银组详解}}}$$

题目描述

Farmer John 计划为奶牛们新开办一所大学！

有 $N$ 头奶牛可能会入学。

每头奶牛最多愿意支付 $c _ i$ 的学费。

Farmer John 可以设定所有奶牛入学需要支付的学费。

如果这笔学费大于一头奶牛愿意支付的最高金额，那么这头奶牛就不会入学。

Farmer John 想赚尽可能多的钱，从而可以给他的讲师提供一笔可观的工资。

请求出他能赚到的钱的数量，以及此时应当收取多少学费。

输入格式

输入的第一行包含 $N$。

第二行包含 $N$ 个整数 $c _ 1, c _ 2, \cdots, c _ N$，其中 $c _ i$ 是奶牛 $i$ 愿意支付的最高学费金额。

输出格式

输出 Farmer John 可以赚到的最大金额以及最优情况下他应该收取的学费。如果有多个解，输出收取学费最小的解。

注意这个问题涉及到的整数可能需要使用 $64$ 位整数型（例如，Java 中的 “long”，C/C++ 中的 “long long”）。

数据范围

$1 \le N \le 10 ^ 5,$
$1 \le c _ i \le 10 ^ 6$。

输入样例：

4
1 6 4 6

输出样例：

12 4

样例解释

如果 Farmer John 收费 $4$，那么 $3$ 头奶牛将会入学，从而使他赚取 $3 \times 4 = 12$ 的金额。

解题思路

本次 $\text {USACO 12}$ 月月赛铜组第一题。

我们可以先把 $c _ i$ 从小到大排好序。FJ 肯定 取 $c _ i$ 中的某个值。粗略的证明：

反证法。如果 FJ 收取的学费不为 $c _ i$ 中的某个数，不妨设 $c _ 1 \le c _ 2 \le \cdots \le c _ n$，FJ 收取学费 $x$ 满足 $c _ {i - 1} < x < c _ i$（$x$ 一定不会大于 $c _ n$，否则没有奶牛愿意上学），那么有 $n - i + 1$ 头奶牛（$i \sim n$）愿意上学，总赚的钱数为 $x \times (n - i + 1)$。但是如果收费 $c _ i$ 的话，FJ 所赚的钱数为 $c _ i \times (n - i + 1) > x \times (n - i + 1)$，肯定比收费 $x$ 更优。故假设不成立，FJ 收取的学费为 $c _ i$ 中的某个值。

我们从 $1$ 到 $n$ 枚举 $c _ i$，对于 $1 \le i \le n$，FJ 可赚到 $\mathbf {c _ i \times (n - i + 1)}$ 的钱（学费 $c _ i$，有 $n - i + 1$ 头奶牛）。我们记 $now = c _ i \times (n - i + 1)$，更新最大值 $mx$ 和最优收费（答案）$ans$。

AC Code

#include <cstdio>
#include <algorithm>
#define N 100005
using namespace std;

int n, ans, a[N];
long long now, mx;

int main ()
{
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++)
    {
        scanf ("%d", &a[i]);
    }
    sort (a + 1, a + n + 1); // 排好序
    for (int i = 1; i <= n; i ++)
    {
        now = (long long) a[i] * (n - i + 1); // 学费为 c[i] 时 FJ 所赚的钱数
        if (now > mx) // 如果这时的钱数大于最大值
        {
            mx = now, ans = a[i]; // 最大值等于当前所赚钱数，更新答案
        }
    }
    printf ("%lld %d", mx, ans); // 输出最大值和答案
    return 0;
}

感谢观看！

上一篇

下一篇

$$\href {/blog/content/29204/} {\color {LimeGreen} {【寒假每日一题】题解}}$$