链接：https://ac.nowcoder.com/acm/contest/6173/C

时间限制：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)。

输出描述:

每组数据输出一行一个实数表示最小花费，保留一位小数。
示例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

思路

这道题主要是计算凳子的数量bds，因为要既有购物车又有凳子，才能把此时购物车中最贵的物品半价。所以如果凳子数量大于购物车数量，那么也只能将购物车数量那么多个物品半价购买。所以我们只需要在计数完成之后加个判断，如果大于购物车数那么就将其bds设置为购物车数那么多。最后在计算最少花费前将输入的价钱按照从从大到小排列，前bds个只需要半价（这样可以使花费最少）。最后保留一位小数输出sum.

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
double a[1005],b[1005],sum=0;
double cmp(double x,double y){
    return x>=y;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m,bds=0;
        sum=0;
        cin>>n>>m;
        for(int i=1;i<=n;++i){
            cin>>a[i]>>b[i];
            if(b[i]==1){
                bds+=1; 
            }
        }
        if(bds>m){
            bds=m;
        }
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++){
            if(i<=bds){
                sum+=a[i]/2.0;
            }
            else{
                sum+=a[i];
            }
        }
        printf("%.1lf\n",sum);
    }
    return 0;
}