做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2958. -- 收购裁判

2958: 收购裁判

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

在足球比赛中,如果你拥有了裁判,那么你的球队至少不会输(因为只要对手进球,那么裁判就说进球无效)。现在,对方在裁判的心目中已经获 得了M分,所有我们也要给裁判大于M分。(当然你在裁判心目中的分数越高好)。裁判有N个亲戚,每个亲戚和裁判的熟悉程度为Wi,收购代价为Vi。每个亲戚只能收买1次请问,如何收购性价比最高?

输入

输入包括多组数据数据 ,每组数据 第一行两个整数M,N

第二行N个整数,表示Wi

第三行N个整数,表示Vi

当N=M=0时输入结束

输出

对于每组样例输出一个三位小数,表示最高的性价比

若无法收购裁判,请输出"NO SOLUTlON"

样例输入

5 10
1 2 3 4 5
5 6 7 8 9
5 10
1 2 3 4 5
2 3 4 5 6
0 0

样例输出

0.500
0.800

提示

样例1、2解释:选3、4、5这三个亲戚

对于20%的数据: N<=10,m<=15,wi<=10

对于50%的数据:N<=100,M<=10000,wi<=10

对于70%的数据:N<=1000,M<=10000,wi<=100

对于100%的数据:N<=1000,M<=10000,wi<=500

标签

[上一题][提交][讨论版][状态][下一题]