A2093 | KC 喝咖啡
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
话说 KC 和 SH 在福州的时候常常跑去 85°C 喝咖啡或者其他的一些什么东西。
这天,KC 想要喝一杯咖啡,服务员告诉他,现在有 $n$ 种调料,这杯咖啡只可以加入其中的 $m$ 种(当然 KC 一定会加入 $m$ 种,不会加入少于 $m$ 种的调料),根据加入的调料不同,制成这杯咖啡要用的时间也不同,得到的咖啡的美味度也不同。
KC 在得知所有的 $n$ 种调料后,作为曾经的化竞之神的他,马上就知道了所有调料消耗的时间 $c _ i$ 以及调料的美味度 $v _ i$。由于 KC 急着回去刷题,所以他想尽快喝到这杯咖啡,但他又想喝到美味的咖啡,所以他想出了一个办法,他要喝到 $\dfrac{\sum v _ i}{\sum c _ i}$ 最大的咖啡,也就是单位时间的美味度最大的咖啡。
现在,KC 把调料信息告诉了 SH,要 SH 帮他算出喝到的咖啡的 $\dfrac{\sum v _ i}{\sum c _ i}$,但 SH 不想帮 KC 算这东西,于是 KC 就只能拜托你来算了。
注释:$\sum$ 表示求和,所以 $\dfrac{\sum v _ i}{\sum c _ i}$ 表示美味度的总和除以消耗时间的总和。
这天,KC 想要喝一杯咖啡,服务员告诉他,现在有 $n$ 种调料,这杯咖啡只可以加入其中的 $m$ 种(当然 KC 一定会加入 $m$ 种,不会加入少于 $m$ 种的调料),根据加入的调料不同,制成这杯咖啡要用的时间也不同,得到的咖啡的美味度也不同。
KC 在得知所有的 $n$ 种调料后,作为曾经的化竞之神的他,马上就知道了所有调料消耗的时间 $c _ i$ 以及调料的美味度 $v _ i$。由于 KC 急着回去刷题,所以他想尽快喝到这杯咖啡,但他又想喝到美味的咖啡,所以他想出了一个办法,他要喝到 $\dfrac{\sum v _ i}{\sum c _ i}$ 最大的咖啡,也就是单位时间的美味度最大的咖啡。
现在,KC 把调料信息告诉了 SH,要 SH 帮他算出喝到的咖啡的 $\dfrac{\sum v _ i}{\sum c _ i}$,但 SH 不想帮 KC 算这东西,于是 KC 就只能拜托你来算了。
注释:$\sum$ 表示求和,所以 $\dfrac{\sum v _ i}{\sum c _ i}$ 表示美味度的总和除以消耗时间的总和。
输入格式
输入数据共三行。
第一行为一个整数 $n, m$,表示调料种数和能加入的调料数。
接下来两行,每行为 $n$ 个数,第一行第 $i$ 个整数表示调料 $i$ 的美味度 $v _ i$,第二行第 $i$ 个整数表示调料 $i$ 消耗的时间 $c _ i$。
第一行为一个整数 $n, m$,表示调料种数和能加入的调料数。
接下来两行,每行为 $n$ 个数,第一行第 $i$ 个整数表示调料 $i$ 的美味度 $v _ i$,第二行第 $i$ 个整数表示调料 $i$ 消耗的时间 $c _ i$。
输出格式
一个实数 $T$,表示 KC 喝的咖啡的最大 $\dfrac{\sum v _ i}{\sum c _ i}$,保留三位小数。
输入输出样例
输入 #1
3 2 1 2 3 3 2 1
输出 #1
1.667
**样例 1 解释**:
KC 选 $2$ 号和 $3$ 号调料,$\dfrac{\sum v _ i}{\sum c _ i} = \dfrac{2 + 3}{2 + 1} = 1.667$。
可以验证不存在更优的选择。
**数据范围**:
对 $20 \%$ 的数据:$1 \leq n \leq 5$。
对 $50 \%$ 的数据:$1 \leq n \leq 10$。
对 $80 \%$ 的数据:$1 \leq n \leq 50$。
对 $100 \%$ 的数据:$1 \leq n \leq 200, 1 \leq m \leq n, 1 \leq c[i], v[i] \leq 1 \times 10 ^ 4$。
数据保证答案不超过 $1000$。
KC 选 $2$ 号和 $3$ 号调料,$\dfrac{\sum v _ i}{\sum c _ i} = \dfrac{2 + 3}{2 + 1} = 1.667$。
可以验证不存在更优的选择。
**数据范围**:
对 $20 \%$ 的数据:$1 \leq n \leq 5$。
对 $50 \%$ 的数据:$1 \leq n \leq 10$。
对 $80 \%$ 的数据:$1 \leq n \leq 50$。
对 $100 \%$ 的数据:$1 \leq n \leq 200, 1 \leq m \leq n, 1 \leq c[i], v[i] \leq 1 \times 10 ^ 4$。
数据保证答案不超过 $1000$。
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?