链接：https://ac.nowcoder.com/acm/contest/20960/1037
来源：牛客网

题目描述

你要买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
一道简单的贪心问题，贪心策略为取购物车和凳子数量的最小值为可以打折的商品数量。然后挑最大的打折就可以了。
AC代码： 
#include <bits/stdc++.h>


using namespace std;

struct Node {
    double price;
    int is_stool;
};

Node a[1005];

bool comp(Node n1, Node n2) {
    return n1.price>=n2.price;
}

int main() {
    int t;
    cin>>t;
    while (t--){
        int n, m;
        int cnt = 0;
        cin>>n>>m;
        for (int i=0;i<n;i++) {
            cin>>a[i].price;
            cin>>a[i].is_stool;
            if (a[i].is_stool==1) cnt++;
        }
        int half_num = min(m, cnt);
        double ans = 0;
        sort(a, a+n, comp);
        for (int i=0;i<n;i++) {
            if (half_num-i>0) ans+=a[i].price/2;
            else ans += a[i].price;
        }
        printf("%.1lf\n",ans);
    }
    
    
    return 0;
}