专栏首页小L的魔法馆2018 Wannafly summer camp Day3--Shopping

2018 Wannafly summer camp Day3--Shopping

Shopping 描述 题目描述: 你要买n件物品,其中有一些是凳子。

商场正在举行促销活动,如果购物车中有至少一个凳子,那么你可以半价购买这个购物车中最贵的一个物品。

你有mm辆购物车,请最小化你的花费。

输入: 第一行一个整数tt表示数据组数 (1≤t≤100)(1≤t≤100)(1\leq t\leq 100)。

每组数据第一行两个整数n,m(1≤n,m≤1000)n,m(1≤n,m≤1000)n,m (1\leq n,m\leq 1000),接下来n行每行两个整数 ai,biai,bia_i,b_i ,分别表示第ii件物品的价格以及它是否是凳子 (1≤a_i≤105,0≤b_i≤1)(1≤a_i≤105,0≤b_i≤1)(1\leq a\_i\leq 10^5,0\leq b\_i\leq 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为凳子个数
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
int t, n, m,a[1005], b, cnt;
double ans;
bool cmp(int a, int b){return a > b;}
int main(void) {
    cin >> t;
    while (t-- > 0) {
        cin >> n >> m;
        cnt = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i] >> b;
            if (b == 1)
                cnt++;
        }
        sort(a, a + n, cmp);
        cnt = min(cnt, m);
        for (int i = 0; i < n; i++) {
            if (i < cnt)
                ans += a[i] * 0.5;
            else
                ans += a[i];
        }
        printf("%.1lf\n", ans);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛--J-强迫症的序列

    链接:https://www.nowcoder.com/acm/contest/90/J 来源:牛客网

    Enterprise_
  • 断言assert()与调试帮助

    对expr求值,如果expr为假,则输出信息并终止程序,反之则什么也不做。 用来检查”不会发生”的条件。 assert的行为依赖与NDEBUG的预处理变...

    Enterprise_
  • BFS算法入门--POJ3984

    迷宫问题–POJ3984 Time Limit: 1000MS Memory Limit: 65536K Total Submissions:...

    Enterprise_
  • 第十八章 VNC远程连接

    我们知道在数据中心机房中,服务器一般是锁在机柜中的,服务器只有在刚买来第一次配置或安装系统时,才会连接显示器、键盘、鼠标等外设,初次配置完毕后,就会把这些外设都...

    晓天
  • C# CsRedis的初探(五)-- Redis常用命令整理(集合类型)

    sadd 命令用来向集合中增加一个或多个元素,如果键不存在则会自动创建。因为在一个集合中不能有相同的元素,所以如果要加入的元素已经存在与集合中...

    Vaccae
  • openshift 使用curl命令访问apiserver

    使用oc(同kubectl)命令访问apiserver资源的时候,会使用到/root/.kube/config文件中使用的配置。

    charlieroro
  • 【Oracle字符集】识别及转换导出文件的字符集

    编辑手记:很多人在进行数据库导入导出操作的时候会遇到字符集的问题,今日拣选了 《循序渐进Oracle》一书中的相关章节,希望对初学Oracle的朋友有所帮助。 ...

    数据和云
  • 使用QtScript库解析Json数组例子

    本文转载自:http://blog.sina.com.cn/s/blog_671732440100uwxh.html

    ccf19881030
  • 马化腾:王者荣耀玩得比较少 吃鸡游戏是当前重点

    12月4日下午消息,第四届世界互联网大会于2017年12月3日—5日在浙江省乌镇举行,在今日下午企业家代表集体采访中,腾讯董事会主席兼首席执行官马化腾表示,腾讯...

    企鹅号小编
  • 科大讯飞李伟:人机交互如何选择合适的「耳朵」

    AI 研习社按:人工智能当前正处于爆发阶段,语音交互作为人工智能的重要组成部分正在各行业全面的落地,在人机进行语音交互的过程中,机器需要通过耳朵实现听觉的作用。

    AI研习社

扫码关注云+社区

领取腾讯云代金券