同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1650_01分数规划

2022-5-16 18:17| 发布者: Hocassian| 查看: 56| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-8950478544500-Problem List-采集的数据-后羿采集器.html

Pro.ID

1650

Title

01 分数规划

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1650

AC

Submit

Ratio

100.00%

时间&空间限制

Time Limit: 60000/60000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

描述

这是一道模板题。

给你 n 个物品，每个物品有两个属性 a_i 和 b_i ，求一组解 x_i ( 1 ≤ i ≤ n, x_i = 0 或 1 ) 使

最大，且恰好有 k 个 x_i 为 1 。

请求出这个最大值。

输入

第一行两个数 n ，k 。 1 ≤ k ≤ n ≤ 10⁵

第二行 n 个数，依次表示 a₁, a₂, ..., a_n 。

第三行 n 个数，依次表示 b₁, b₂, ..., b_n 。

1 ≤ a_i ≤ b_i ≤ 10⁶

输出

Description

这是一道模板题。

给你 n 个物品，每个物品有两个属性 a_i 和 b_i ，求一组解 x_i ( 1 ≤ i ≤ n, x_i = 0 或 1 ) 使

最大，且恰好有 k 个 x_i 为 1 。

请求出这个最大值。

Input

第一行两个数 n ，k 。 1 ≤ k ≤ n ≤ 10⁵

第二行 n 个数，依次表示 a₁, a₂, ..., a_n 。

第三行 n 个数，依次表示 b₁, b₂, ..., b_n 。

1 ≤ a_i ≤ b_i ≤ 10⁶

Output

一行，一个实数，精确到小数点后 4 位。

Sample Input

Sample #1
5 3
1 2 4 1 2
4 3 9 3 7

Sample #2
3 2
5 0 2
5 1 6

Sample #2
10 6
1 5 3 7 2 8 5 4 2 6
15 35 12 12 9 15 7 7 13 15

Sample Output

Sample #1
0.4667

Sample #2
0.8333

Sample #2
0.4923

样例输入