USACO2022铜组 T1 题解

· · 题解

（1.16：本题解进行了一些修改，希望管理能给通过 /kel）

题意：

有 N（1 \le N \le 10^5）头奶牛可能会入学。每头奶牛最多愿意支付 c_i 的学费（1 \le c_i\le 10^6）。 Farmer John 可以设定所有奶牛入学需要支付的学费。如果这笔学费大于一头奶牛愿意支付的最高金额，那么这头奶牛就不会入学。Farmer John 想赚尽可能多的钱，从而可以给他的讲师提供一笔可观的工资。请求出他能赚到的钱的数量，以及此时应当收取多少学费。

33 分做法

虽然是 T1，但是纯暴力是过不去的哦。

枚举答案，然后再遍历一遍数组判断当前奶牛能否支付起现在的学费，不断取 \operatorname{max} 就行了。

设 k 是 c_i 中最大的数字，这种暴力的做法时间复杂度即 \mathcal{O}(nk)，因为 k \le 10^6，所以明显会 TLE。

放一下代码吧。

#include<iostream>
#define int long long//不开ll见祖宗（
using namespace std;
int n,a[100001],ans,k,cnt,mx;
signed main(){
    cin>>n;
    for(int i = 1;i<=n;i++) {
        cin>>a[i];
        k = max(k,a[i]);
    }
    for(int i = 1;i<=k;i++){//枚举答案
        ans = 0;
        for(int j = 1;j<=n;j++){
            if(a[j]>=i) ans+=i;//判断第 j 头奶牛能否支付起当前的学费 i
        }
        if(ans>mx){//打擂台取最大
            mx = ans;
            cnt = i;
        }
        if(ans==mx){//如果答案相同取学费小的
            cnt = min(cnt,i);
        }
    }
    cout<<ans<<' '<<cnt<<endl;
    return 0;
}

100 分做法（满分）

可以证明，取的最佳学费永远是 c_i 的其中之一（因为如果不是，可以稍微增加学费而不改变付钱的牛）。

因此，我们所要做的就是维护这些值，看看每个值能赚多少钱。

我们先排一下序，确定有多少奶牛可以支付当前的学费，然后从最低到最高进行更新，维护愿意支付的奶牛数量的计数。（在一个 c_i 值被遍历到后，这些奶牛就不再能够支付学费，所以计数是递减）

这些操作在 \mathcal{O}(n \log n) 的时间复杂度就可以解决力（喜

还有最重要的一件事，就是 不开 \textbf{long long} 见祖宗，因为答案可能高达 10^5 \times 10^6 = 10^{11}。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000001],ans,cnt;
signed main() {
    cin>>n;
    int cow = n;
    for (int i = 1; i<=n; i++) cin>>a[i];
    sort(a+1,a+n+1);
    for (int i = 1; i<=n; i++) {
        if (a[i]*cow>ans) {//最优答案更新 
            ans = a[i]*cow;
            cnt = a[i];
        }
        cow--;//第i-1头牛不交学费了。 
    }
    cout<<ans<<' '<<cnt<<endl;
    return 0;
}
一些魔怔的废话：作者因为评测机原因这道题抱灵力！谢谢你，USACO。