uvalive 3971 Assemble

时间:2022-03-27 00:47:01

https://vjudge.net/problem/UVALive-3971

题意:

现在你要组装一台电脑,每个电脑的一种类型的配件都有多种选择,它们的名字是不同的。

现在给出已有的元件,每种类型都至少有一个元件。你有已知的预算,要求你找出以不超过预算的钱,每种类型的元件恰好选择一个,最低质量的元件的质量要尽量高,输出这个最高值。

思路:

从题意的叙述来看,最大化最小值,那么肯定是选用二分。

二分选择的量应该是质量。

接下来证明花费的钱是随着质量非递减的。

设当前的最小质量为x,那么把所有元件中质量小于x的全部删除,在剩下元件中,每一类型选择价钱最少的。

当x增加:

1.选择的价钱最少的恰好是质量最小的,那么此时质量选更大的话,价格的总和就有可能变大(会有重复的价格);

2.选择的价钱最少的不是质量最小的,那么当质量更大的话,选择的还是这个元件,价钱不会增加。

所以,当x逐渐增大的时候,价钱非递减,满足而二分的条件。

代码:

 #include <stdio.h>
#include <string.h>
#include <string>
#include <map>
#include <vector>
using namespace std; struct node
{
long long p,q;
}; int cnt = ;
vector<node> v[];
int n;
long long b;
map<string,int> mmp; bool meet(long long k)
{
long long sum = ; for (int i = ;i <= cnt;i++)
{
long long minn = 1e15; for (int j = ;j < v[i].size();j++)
{
if (v[i][j].q >= k)
{
if (v[i][j].p < minn)
{
minn = v[i][j].p;
}
}
} sum += minn;
} return sum <= b;
} int main()
{
int t; scanf("%d",&t); while (t--)
{
scanf("%d%lld",&n,&b); for (int i = ;i <= n;i++) v[i].clear(); mmp.clear(); cnt = ; for (int i = ;i < n;i++)
{
char s1[],s2[];
long long p,q; scanf("%s%s%lld%lld",s1,s2,&p,&q); if (mmp[s1])
{
v[mmp[s1]].push_back(node{p,q});
}
else
{
mmp[s1] = ++cnt;
v[cnt].push_back(node{p,q});
}
} long long l = ,r = 1e11; while (r > l + )
{
long long mid = (l + r) >> ; if (meet(mid)) l = mid;
else r = mid;
} while (meet(l+)) l++; printf("%lld\n",l);
} return ;
}

uvalive 3971 Assemble的更多相关文章

  1. uvalive 3971 - Assemble&lpar;二分搜索 &plus; 贪心)

    题目连接:3971 - Assemble 题目大意:有若干个零件, 每个零件给出的信息有种类, 名称, 价格, 质量,  现在给出一个金额, 要求在这个金额范围内, 将每个种类零件都买一个, 并且尽量 ...

  2. UVALive 3971 Assemble&lpar;模拟 &plus; 二分&rpar;

    UVALive 3971 题意:有b块钱.想要组装一台电脑,给出n个配件的种类,名字,价格,品质因子.若各种类配件各买一个,总价格<=b,求最差品质配件的最大品质因子. 思路: 求最大的最小值一 ...

  3. UVALive 3971 Assemble(二分&plus;贪心)

    本题思路不难,但是要快速准确的AC有点儿考验代码功力. 看了大白书上的标程,大有所获. 用map和vector的结合给输入分组,这个数据结构的使用非常精美,恰到好处. #include<iost ...

  4. UVaLive 3971 Assemble &lpar;水题二分&plus;贪心&rpar;

    题意:你有b元钱,有n个配件,每个配件有各类,品质因子,价格,要每种买一个,让最差的品质因子尽量大. 析:很简单的一个二分题,二分品质因子即可,每次计算要花的钱的多少,每次尽量买便宜且大的品质因子. ...

  5. UVA 12124 UVAlive 3971 Assemble&lpar;二分 &plus; 贪心&rpar;

    先从中找出性能最好的那个数, 在用钱比較少的去组合,能组出来就表明答案在mid的右边,反之在左边, #include<string.h> #include<map> #incl ...

  6. UVALive 3971 组装电脑

    https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_probl ...

  7. Uva 12124 Uva Live 3971 - Assemble 二分&comma; 判断器&comma; g&plus;&plus;不用map&period;size&lpar;&rpar; 难度&colon;0

    题目 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_pr ...

  8. LA 3971 Assemble(二分)

    题目: 给你b元钱,让你组装一台电脑,有n个配件,属性有 种类 名字 价格 品质,每种类型选至少一个,并且最小品质最大.输出这个最大的最小品质. 白书上说了,最小值最大的问题一般是二分来求解答案.在这 ...

  9. LA 3971 &lpar;二分&rpar; Assemble

    题意: 你有b块钱想要组装一台电脑.给出n个配件的种类,品质和价格,要求每个种类的配件各买一个总价格不超过b且“品质最差配件”的品质因子应尽量大. 这种情况下STL的map的确很好用,学习学习 这种最 ...

随机推荐

  1. textFiled的placeHolder字体颜色

    self.title=@"修改UITextField的placeholder字体颜色"; UITextField *textTF=[[UITextField alloc]initW ...

  2. 创意设计展示:折叠效果在移动 App 中的应用

    在今天在移动 App 界面设计中,你可以看到不同创意类型的视觉效果.特别是在 Dribbble 上面,有有很多应用程序的 UI 概念设计,让你惊叹.当然,他们大多只是作为一个概念设计,可能永远也不会成 ...

  3. Java中使用BASE64加密&amp&semi;解密

    package com.bao.tools.encryption; import java.io.IOException; import org.junit.Test; import sun.misc ...

  4. Android ScaleAnimation类:尺寸变化动画类

    ScaleAnimation类是Android系统中的尺寸变化动画类,用于控制View对象的尺寸变化,该类继承于Animation类. ScaleAnimation类中的很多方法都与Animation ...

  5. 在sphinx中应用复杂过滤条件

    一.问题的引入   在sphinx应用中,需要对数据进行复杂的条件过滤,刷选出我们需要的数据.这个过程,等同于mysql查询中的where条件.   但sphinx本身的filter并不能支持复杂的逻 ...

  6. 实现一个简单的FTP服务器&lpar;十四&rpar;

    此为一个网络编程的一个系列,后续会把内容补上...

  7. Sublime 学习记录(五) Sublime 其他插件&lpar;个人喜好&rpar;

    (一)  JSFormat 安装 :命令面板 pci 回车 JSFormat 回车 功能 : javascript的代码格式化插件 简介 : 很多网站的JS代码都进行了压缩,一行式的甚至混淆压缩,这让 ...

  8. OKMX6Q在ltib生成的rootfs基础上制作带QT库的根文件系统

    ltib每次执行后会在其目录下生成rootfs目录,并以其为基础生成rootfs.ext2.gz文件,而litb自带的QT库又太老,所以想到按照飞凌的<OKMX6X-S2-Qt4.8.5移植手册 ...

  9. Python3基础 list insert 在指定位置挤入一个元素

             Python : 3.7.0          OS : Ubuntu 18.04.1 LTS         IDE : PyCharm 2018.2.4       Conda ...

  10. Excel数据导入PG库,字符串正则表达式

    1.Excel数据导入到PG库的某张表中:先将Excel文件转换为CSV格式,打开SQL Shell(psql),连接数据库(输入server,database,Port,username),然后再执 ...