Shopping

题目

要买 n 件物品，其中有一些是凳子。
商场正在举行促销活动，如果购物车中有至少一个凳子，那么可以半价购买这个购物车中最贵的一个物品。
现有 m 辆购物车，求最少的花费。

解题思路

将非凳子的价格录入 item1，将凳子的价格录入 item2。
对 item1 和 item2 进行从大到小排序。

如果还有新的购物车，将价格最贵的物品放入其中，

• 如果该物品是凳子，价格减半。
• 如果不是凳子，将价格最小的凳子放入其中，最贵的物品价格减半；如果没有凳子，物品原价。

如果没有新的购物车，将剩下的东西随便放置其中一个购物车，物品原价。

C++代码

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int t;
    scanf("%d", &t);
    int n, m;
    while(t--){
        scanf("%d%d", &n, &m);
        vector<int> item1, item2;
        int a, b;
        for(int i=0; i<n; ++i){
            scanf("%d%d", &a, &b);
            if(b==0)
                item1.push_back(a);
            else
                item2.push_back(a);
        }
        sort(item1.rbegin(), item1.rend());
        sort(item2.rbegin(), item2.rend());
        int k = 0;
        double sum = 0;
        for(int i=0; i<item2.size();){
            if(m > 0){
                if(k<item1.size() && item1[k]>item2[i]){
                    sum += item1[k]*0.5;
                    sum += item2.back();
                    item2.pop_back();
                    ++k;
                }
                else{
                    sum += item2[i]*0.5;
                    ++i;
                }
                --m;
            }
            else{
                sum += item2[i];
                ++i;
            }
        }
        for(; k<item1.size(); ++k)
            sum += item1[k];
        printf("%.1f\n", sum);
    }
    return 0;
}