本文主要是介绍【upc 9523】Shopping II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
你要买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>
#define fin freopen("in.txt","r",stdin)
#define fout freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int MAX = 1e3 + 5;
const int inf = 0x3f3f3f3f;
int a[MAX];
int n, m;
int main() {// fin;int t;scanf("%d",&t);while(t--) {scanf("%d%d",&n,&m);int cnt = 0;for(int x,i=1;i<=n;++i) {scanf("%d%d",&a[i],&x);if(x) cnt++;}sort(a+1,a+n+1);double ans = 0;cnt = min(m,cnt);for(int i=n;i>=1;--i) {if(cnt <= 0) ans += a[i];else ans += 0.5*a[i];--cnt;}printf("%.1f\n",ans);}return 0;
}
这篇关于【upc 9523】Shopping II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
