TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3484
  • 题目
  • P3484旅行
    限制 : 时间限制 : 30000 MS   空间限制 : 165536 KB
    问题描述

    Mr_H 旗下的 n 个OIer 坐船外出旅行!
    但是他们只有一艘船,虽然船能装下全部的Oier,但太拥挤将会影响众OIer 的心情,所以Mr_H决定选择一部分Oier 去。我们假设,每个人单独坐船的快乐程度是Ci,而船上每多一个人,他的快乐程度会减去Di。
    现在你的任务是帮助Mr_H 计算,选择那些人,才能使船上所有人的快乐程度之和达到最大。

    输入格式

    第 1 行是一个整数n,表示OIer 的人数;
    第 2 行有n 个整数,第i 个整数表示第i 个人人单独坐船的快乐程度Ci(1<=Ci<=10000);
    第 3 行有n 个整数,第i 个整数表示每多1 人,第i 个人快乐程度的下降值Di(1<=Di<=10)。

    输出格式

    第 1 行一个整数,是最大的快乐程度之和;
    第 2 行一个整数,是最大的快乐程度之和所对应的汽艇上的人数(若有多种方案,则输出人数最多的)。

    样例输入

    6
    10 10 10 10 10 9
    2 2 2 2 2 3

    样例输出

    18
    3

    提示

    【样例解释】
    前 3 个人去坐汽艇可使快乐程度之和达到最大,每个人的快乐程度均为10-2*2=6,总和是18。
    【数据范围】
    对于 30%的数据,n<=20;
    对于100%的数据,n<=1000。


    来源  by YZ