Cow College

题意

有 N 头牛，每头牛最多愿意支付 c_i 的学费。

FJ 要统一设置一个学费 p。只有满足 $c_i >= p$ 的牛会入学，每头入学的牛都支付 p。

求最大收入；如果有多个学费都能达到最大收入，输出最小的学费。

思路

暴力想法

可以枚举每一个可能学费，再统计愿意支付的牛数：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 13:10
 * update_at: 2026-07-11 13:13
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;
int cost[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    int max_cost = 0;
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
        if (max_cost < cost[i]) {
            max_cost = cost[i];
        }
    }

    long long best_money = -1;
    int best_tuition = 0;

    // 暴力枚举每一种可能学费，只适合 max_cost 很小的数据。
    for (int tuition = 1; tuition <= max_cost; tuition++) {
        int cows = 0;
        for (int i = 1; i <= n; i++) {
            if (cost[i] >= tuition) {
                cows++;
            }
        }

        long long money = 1ll * tuition * cows;
        if (money > best_money) {
            best_money = money;
            best_tuition = tuition;
        }
    }

    cout << best_money << ' ' << best_tuition << '\n';

    return 0;
}

如果直接枚举 1..max(c_i)，每个学费都扫一遍所有牛，复杂度是 $O(N \max c_i)$ ，会超时。

只枚举 `c_i`

官方解析的关键结论是：最优学费一定可以取某个 c_i。

如果一个学费 p 夹在两个相邻的 c_i 之间，那么在不超过下一个 c_i 之前，提高 p 不会改变愿意支付的牛集合，却会增加收入。所以这种 p 不需要考虑。

把 c_i 从小到大排序。枚举 cost[i] 作为学费时，所有从 i 到 n 的牛都愿意支付，所以收入为：

cost[i] \times (n - i + 1)

从小到大扫描候选学费，只在收入严格变大时更新答案。这样如果收入相同，答案会保留较小的学费。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 13:10
 * update_at: 2026-07-11 13:13
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
long long cost[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
    }

    sort(cost + 1, cost + n + 1);

    long long best_money = -1;
    long long best_tuition = 0;

    for (int i = 1; i <= n; i++) {
        long long cows = n - i + 1; // 愿意支付 cost[i] 的牛数量。
        long long money = cost[i] * cows;

        // 从低学费到高学费扫描，收益相同则保留更小的学费。
        if (money > best_money) {
            best_money = money;
            best_tuition = cost[i];
        }
    }

    cout << best_money << ' ' << best_tuition << '\n';

    return 0;
}

复杂度

排序复杂度为 $O(N \log N)$ ，枚举候选学费为 $O(N)$ ，总时间复杂度为 $O(N \log N)$ 。

空间复杂度为 $O(N)$ 。

最大收入可达 $10^{11}$ ，需要使用 long long。

总结

这题的重点不是复杂实现，而是先减少候选学费。

只要证明“最优学费可以取某个 c_i”，排序后每个候选的支付人数就是一个后缀长度，收入就能直接算出来。

目录

题意

思路

暴力想法

只枚举 c_i

代码

复杂度

总结

只枚举 `c_i`