Shopping 描述 题目描述: 你要买n件物品,其中有一些是凳子。
商场正在举行促销活动,如果购物车中有至少一个凳子,那么你可以半价购买这个购物车中最贵的一个物品。
你有mm辆购物车,请最小化你的花费。
输入: 第一行一个整数tt表示数据组数 (1≤t≤100)(1≤t≤100)(1\leq t\leq 100)。
每组数据第一行两个整数n,m(1≤n,m≤1000)n,m(1≤n,m≤1000)n,m (1\leq n,m\leq 1000),接下来n行每行两个整数 ai,biai,bia_i,b_i ,分别表示第ii件物品的价格以及它是否是凳子 (1≤a_i≤105,0≤b_i≤1)(1≤a_i≤105,0≤b_i≤1)(1\leq a\_i\leq 10^5,0\leq b\_i\leq 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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
int t, n, m,a[1005], b, cnt;
double ans;
bool cmp(int a, int b){return a > b;}
int main(void) {
cin >> t;
while (t-- > 0) {
cin >> n >> m;
cnt = 0, ans = 0;
for (int i = 0; i < n; i++) {
cin >> a[i] >> b;
if (b == 1)
cnt++;
}
sort(a, a + n, cmp);
cnt = min(cnt, m);
for (int i = 0; i < n; i++) {
if (i < cnt)
ans += a[i] * 0.5;
else
ans += a[i];
}
printf("%.1lf\n", ans);
}
return 0;
}