P2707 Facer帮父亲

    • 197通过
    • 410提交
  • 题目提供者 _Sugar_
  • 评测方式 云端评测
  • 标签 二叉堆 数论,数学 洛谷原创 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    Facer可是一个孝顺的孩纸呦

    题目描述

    Facer的父亲是一名经理,现在总是垂头丧气的。

    Facer问父亲,怎么啦?父亲说,公司出了点问题啊。

    公司管理着N个风景点,每个风景点都有不少人来参观。

    可是现在!人民投诉票价太高了,他不得不调整票价

    具体来说,第i个景点如果票价是x,来的人数就是max( (ai - bi * x),0 )[收益自己算好伐]

    你需要分配每个景点的门票,使得每个景点门票总和不超过k,且最大化收益

    求最大的收益

    输入输出格式

    输入格式:

    第一行N , k

    接下来N行,每行ai,bi

    输出格式:

    一行,最大的收益

    输入输出样例

    输入样例#1: 复制
    2 4
    50 2
    40 1
    输出样例#1: 复制
    171

    说明

    样例解释:

    景点1票价3,景点2票价1

    景点1人数:50 - 3*2 = 44 票价 :3 收益:132

    景点2人数 : 40 - 1*1 = 39 票价 : 1 收益:39

    总收益171 最大

    10%  n <= 5 , k <= 5
    30%  n <= 100,k <= 100
    60%  n <= 2000,k <= 2000
    100%n <= 100000,k <= 100000
    1 <= ai , bi <= 100000
    鸣谢 zhouyonglong 提供解法
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。