AcWing 4818.奶牛大学 题解

形式化题意

给定一个整数 \(N\) 和一个序列 \(c\) ( \(|c|=N\) )，试找出一个最小的 \(x\) ，使得 \(f(x)=(\sum\limits_{i=1}^{N}c_i>=x)\times x\)的值最大

大概思路

由于 \(c_i\) 的最大值只有 \(10^6\) 而 \(N\) 最大只有 \(10^5\) ，因此我们考虑一种 \(O(log_2 N\times Max_{c_i})\) 的做法，即暴力枚举 \([0,Max_{c_i}]\) 中的每一个可能的 \(x\) ，逐个比较得出使得 \(f(x)\) 最大的 \(x\)。

算法设计

我们可以考虑枚举 \(Z\) 中的所有的 \(x\) ，追个比较 \(f(x)\) 的值，并得出满足要求最小的 \(x\) ，但是这样做是不可实现的，因为我们不可能枚举整数集的每一个可能的值。

但是我们可以发现，对于所有的 \(x<0\) ，始终有 \(f(x)<0\)（读者可以试着自己证明一下），而对于 \(f(0)\)，有 \(f(0)=0\)（也请读者想一想这应该如何证明，步骤十分简单）。所以说，我们可以排除所有的负数。

而对于所有的 \(x>Max_{c_i}\) ，都有 \(f(x)=0\) ，那么对于所有的 \(f(x)=0\)，最小的 \(x\) 应该是 \(0\) 。所以我们排除了 \(x>Max_{c_i}\) 的所有情况。

于是，我们只需要枚举 \([0,Max_{c_i}]\) 中的每一个数即可。

至于计算 \(f(x)\) ，我们只需要先将数组排好序，然后找到第一个大于等于 \(x\) 的数 \(c_i\) ，可以证明 \(\sum\limits_{i=1}^{N}c_i>=x\) 等于 \(N-i+1\) （请读者自己想一想为什么），于是 \(f(x)\) 就等于 \((N-i+1)*x\) 。而查找第一个大于等于 \(x\) 的数 \(c_i\) 则可以用二分法实现。总复杂度 \(O(N \times log_2 N +Max_{c_i} \times log_2 N )\)

代码

完整C++代码如下

#include<iostream>
#include<algorithm>
using namespace std;
using UL=unsigned long;
using ULL=unsigned long long;//用于存储大型非负整数
UL c[100005];
int main()
{
    register UL N,maxn(0);//maxn用于计算数组中的最大值
    cin>>N;
    for(register UL i(1);i<=N;++i) {
        cin >> c[i];
        if(c[i]>maxn)
            maxn=c[i];
    }
    sort(c+1,c+1+N);//按照数值排序
    register UL price(0);//price记录当前最优情况下收取的学费
    register ULL ans(0);//ans记录当前的最大答案
    for(register UL i(maxn);i;--i)
    {
        register const UL first(lower_bound(c+1,c+1+N,i)-c);//first:常量UL形式存储第一个大于等于i的元素的下标
        register const ULL income((N-first+1)*(ULL)(i));//常量ULL形式存储当前方案的收入
        if(income>ans)
            ans=income,
            price=i;
        else if(income==ans)
            price=i;
    }
    cout<<ans<<" "<<price;//按照题目要求输出
    return 0;
}