Cow Colledge (USACO Bronze 2022 December)

这是比较直观一个搜索问题。

直接在原始数据上搜索是不行的，因为针对每个价格都需要扫描所有的牛，复杂度 $\mathcal{O}(N\cdot \max c_i)$ ，超过 $10^8$ 了。

对付这个问题的办法是把所有牛按能接受的价格排序，然后当从低到高尝试所有价格时，我们就可以 $\mathcal{O}(1)$ 复杂度判断多少头牛会交学费了，整体复杂度是 $\mathcal{O}(\max c_i)$ 或者 $\mathcal{O}(N)$ 。两种都可以通过。

以下是 $\mathcal{O}(N)$ 的写法。这里用到一个中间结论，是我们只需要试牛能接受的最高价格这些价格点，而不需要试所有可能价格。两个最高价格最接近的牛之间的价格点，肯定不是最优的。因为如果选择了中间的价格，我们把价格提升到上方的牛的出价，能接受的牛的数量不变，而收入提升了，因此中间的价格不需要尝试。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
 
int n,m;
vector<int> p;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        p.push_back(x);
    }
    sort(p.begin(), p.end());
    long long ans = 0;
    int val = 0;
    for (int i = 0; i < n; i++) {
        long long x = (long long)p[i] * (n-i);
        if (x > ans) {
            ans = x;
            val = p[i];
        }
    }
    printf("%lld %d", ans, val);
 
    return 0;
}