1 条题解
-
0
何老师 (root) LV 0 MOD @ 2019-10-14 15:59:39
1、枚举算法
假设小H 以 P[i] 的价格出售,则凡是出价大于等于P[i] 的小朋友可以买到一个玩具,假设有x个小朋友可以买到玩具,则小H 的收入为 P[i] * x;于是得到如下枚举算法:
int Ans=0;
for(int i=1;i<=M;i++)
{
int x=0;
for(int j=1;j<=M;j++)
if(P[j]>=P[i]) x++;
if(x>N) x=N;
Ans=max(Ans,P[i]*x);
}时间复杂度为 \(O(M^2)\)
2、优化
把P[1]..P[M]由大到小排序 后,对于枚举以P[i]出售时,显然P[1]..P[i]这些人都可以买得一个玩具,此时小H的收入为P[i] * i,于是时间复杂度为:
排序时间复杂度为:\(O(nlogn)\)
枚举时间复杂度为:\(O(min(M,N))\)
- 1