题意:n件物品,里面有一些凳子,有m个购物车,每个物品有一个权值a[i]和b[i],分别表示价值大小和是否为凳子,若一个购物车里有凳子,则这个购物车里的价格最高的物品半价
贪心方法:我们可以发现有凳子除了影响半价没有其他影响了,所以我们只需要考虑一下有几个可以半价就可以了,于是我们就可以只计算一下购物车和凳子个数的最小值,然后找到最大的最小值的几个就行了,这几个用半价算,其他就直接加进去就好了
代码:
#include <iostream> #include<cmath> #include<vector> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e5+10; bool cmp(int a,int b) { return a>b; } int main() { int t,n,m; scanf("%d",&t); while(t--) { int a,b; vector<int> dengzi,other; scanf("%d%d",&n,&m); int num[maxn]; int cnt=0; int w=0; for(int i=0;i<n;i++) { scanf("%d%d",&a,&b); num[w++]=a; if(b==1) cnt++; } sort(num,num+w,cmp); int last=min(cnt,m); double ans=0; for(int i=0;i<w;i++) { if(i<last) ans+=1.0*num[i]/2; else ans+=num[i]; } printf("%.1f\n",ans); } return 0; }