题解

1 条题解

  • 0
    @ 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

信息

ID
1326
难度
2
分类
贪心 | 其他 | 排序 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
9
上传者