题目描述

你要买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

分析：

将每一个凳子看成一次打折的机会，然后对所有商品按照价格从大到小排序，让打折机会尽可能用在价格排在前面的商品上（贪心思想）。但是打折机会可能会受到购物车数量的限制，所以我们将打折机会和购物车数量取一个最小值，作为最终的打折次数

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
int t;
int n,m;
const int N=1005;
int a[N],b[N];
bool cmp(int a,int b){
    return a>b;
}
int main(){
    scanf("%d",&t);
    while(t--){
        int cnt=0;//cnt代表打折次数，也就是凳子的个数
        memset(a,0,sizeof(a));//初始化
        memset(b,0,sizeof(b));
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++){
            scanf("%d%d",&a[i],&b[i]);
            if(b[i]==1){
                cnt++;
            }
        }
        sort(a,a+n,cmp);
        cnt=min(cnt,m);//最终打折次数=min(凳子个数，购物车个数)
        double ans=0;
        //统计被打折商品的价格
        for(int i=0;i<cnt;i++){
            ans+=a[i]*1.0/2;
        }
        //统计其他商品的价格
        for(int i=cnt;i<n;i++){
            ans+=a[i];
        }
        printf("%.1lf\n",ans);//最后这里注意保留1位小数
    }
    return 0;
}