链接：https://www.nowcoder.com/acm/contest/203/D
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

你要买n件物品，其中有一些是凳子。
商场正在举行促销活动，如果购物车中有至少一个凳子，那么你可以半价购买这个购物车中最贵的一个物品。
你有m辆购物车，请最小化你的花费。

输入描述

第一行一个整数t表示数据组数 (1 ≤ t ≤ 100)。 每组数据第一行两个整数n,m (1 ≤ n,m ≤ 1000)，接下来n行每行两个整数ai,bi，分别表示第i件物品的价格以及它是否是凳子 (1 ≤ ai ≤ 105, 0 ≤ bi ≤ 1)。

输出描述

每组数据输出一行一个实数表示最小花费，保留一位小数。

输入

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

输出

12.5
10.5

解题思路

min(ans,m),就是可打折的数量，ans是凳子的数量，把价格最大的几个打折就行了。

#include <cstdio>
#include <algorithm>
using namespace std;
int cmp(int A, int B) {
	return A > B;
}
int main()
{
	double sum;
	int t, a, n, m, ans, lep[1010];
	scanf("%d", &t);
	while (t--)
	{
		ans = 0;
		sum = 0;
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; i++)
		{
			scanf("%d%d", &lep[i], &a);
			if (a)
				ans++;
		}
		ans = min(ans, m);
		sort(lep, lep + n, cmp);
		for (int i = 0; i < n; i++)
		{
			if (i < ans)
				sum += lep[i] / 2.0;
			else sum += lep[i];
		}
		printf("%.1f\n", sum);
	}
	return 0;
}