Shopping

描述

题目描述：

你要买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(m,cnt)个物品打折,cnt为凳子个数

1 #include
             
               2 #include
              
                3 #include
               
                 4 #include
                
                  5 using namespace std; 6 int t, n, m,a[1005], b, cnt; 7 double ans; 8 bool cmp(int a, int b){
           return a > b;} 9 int main(void) {10     cin >> t;11     while (t-- > 0) {12         cin >> n >> m;13         cnt = 0, ans = 0;14         for (int i = 0; i < n; i++) {15             cin >> a[i] >> b;16             if (b == 1)17                 cnt++;18         }19         sort(a, a + n, cmp);20         cnt = min(cnt, m);21         for (int i = 0; i < n; i++) {22             if (i < cnt)23                 ans += a[i] * 0.5;24             else25                 ans += a[i];26         }27         printf("%.1lf\n", ans);28     }29     return 0;30 }