menu
大连理工大学 DP·AC算法竞赛协会 ICPC集训队 Online Judge
account_circle
请登录
登录
注册
home
首页
book
题目
library_books
题单
apps
分类
play_circle_outline
状态
layers
竞赛/作业
equalizer
排名
assignment_ind
登录
person_add
注册
1056: Shopping
时间限制：
1.000s
内存限制：
128MB
提交
通过: 7
提交: 11
统计
题目描述
你要买n件物品，其中有一些是凳子。
商场正在举行促销活动，如果购物车中有至少一个凳子，那么你可以半价购买这个购物车中最贵的一个物品。
你有m辆购物车，请最小化你的花费。
输入格式
第一行一个整数t表示数据组数 (1 ≤ t ≤ 100)。
每组数据第一行两个整数n,m (1 ≤ n,m ≤ 1000)，接下来n行每行两个整数a
i
,b
i
，分别表示第i件物品的价格以及它是否是凳子 (1 ≤ a
i
≤ 10
5
, 0 ≤ b
i
≤ 1)。
输出格式
每组数据输出一行一个实数表示最小花费，保留一位小数。
样例输入
content_copy
2 5 1 1 0 2 1 3 1 4 0 5 0 5 10 1 0 2 1 3 1 4 0 5 0
样例输出
content_copy
12.5 10.5
分类
贪心算法
提交