链接: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; }