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的更多相关文章
-
uvalive 3971 - Assemble(二分搜索 + 贪心)
题目连接:3971 - Assemble 题目大意:有若干个零件, 每个零件给出的信息有种类, 名称, 价格, 质量, 现在给出一个金额, 要求在这个金额范围内, 将每个种类零件都买一个, 并且尽量 ...
-
UVALive 3971 Assemble(模拟 + 二分)
UVALive 3971 题意:有b块钱.想要组装一台电脑,给出n个配件的种类,名字,价格,品质因子.若各种类配件各买一个,总价格<=b,求最差品质配件的最大品质因子. 思路: 求最大的最小值一 ...
-
UVALive 3971 Assemble(二分+贪心)
本题思路不难,但是要快速准确的AC有点儿考验代码功力. 看了大白书上的标程,大有所获. 用map和vector的结合给输入分组,这个数据结构的使用非常精美,恰到好处. #include<iost ...
-
UVaLive 3971 Assemble (水题二分+贪心)
题意:你有b元钱,有n个配件,每个配件有各类,品质因子,价格,要每种买一个,让最差的品质因子尽量大. 析:很简单的一个二分题,二分品质因子即可,每次计算要花的钱的多少,每次尽量买便宜且大的品质因子. ...
-
UVA 12124 UVAlive 3971 Assemble(二分 + 贪心)
先从中找出性能最好的那个数, 在用钱比較少的去组合,能组出来就表明答案在mid的右边,反之在左边, #include<string.h> #include<map> #incl ...
-
UVALive 3971 组装电脑
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_probl ...
-
Uva 12124 Uva Live 3971 - Assemble 二分, 判断器, g++不用map.size() 难度:0
题目 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_pr ...
-
LA 3971 Assemble(二分)
题目: 给你b元钱,让你组装一台电脑,有n个配件,属性有 种类 名字 价格 品质,每种类型选至少一个,并且最小品质最大.输出这个最大的最小品质. 白书上说了,最小值最大的问题一般是二分来求解答案.在这 ...
-
LA 3971 (二分) Assemble
题意: 你有b块钱想要组装一台电脑.给出n个配件的种类,品质和价格,要求每个种类的配件各买一个总价格不超过b且“品质最差配件”的品质因子应尽量大. 这种情况下STL的map的确很好用,学习学习 这种最 ...
随机推荐
-
textFiled的placeHolder字体颜色
self.title=@"修改UITextField的placeholder字体颜色"; UITextField *textTF=[[UITextField alloc]initW ...
-
创意设计展示:折叠效果在移动 App 中的应用
在今天在移动 App 界面设计中,你可以看到不同创意类型的视觉效果.特别是在 Dribbble 上面,有有很多应用程序的 UI 概念设计,让你惊叹.当然,他们大多只是作为一个概念设计,可能永远也不会成 ...
-
Java中使用BASE64加密&;解密
package com.bao.tools.encryption; import java.io.IOException; import org.junit.Test; import sun.misc ...
-
Android ScaleAnimation类:尺寸变化动画类
ScaleAnimation类是Android系统中的尺寸变化动画类,用于控制View对象的尺寸变化,该类继承于Animation类. ScaleAnimation类中的很多方法都与Animation ...
-
在sphinx中应用复杂过滤条件
一.问题的引入 在sphinx应用中,需要对数据进行复杂的条件过滤,刷选出我们需要的数据.这个过程,等同于mysql查询中的where条件. 但sphinx本身的filter并不能支持复杂的逻 ...
-
实现一个简单的FTP服务器(十四)
此为一个网络编程的一个系列,后续会把内容补上...
-
Sublime 学习记录(五) Sublime 其他插件(个人喜好)
(一) JSFormat 安装 :命令面板 pci 回车 JSFormat 回车 功能 : javascript的代码格式化插件 简介 : 很多网站的JS代码都进行了压缩,一行式的甚至混淆压缩,这让 ...
-
OKMX6Q在ltib生成的rootfs基础上制作带QT库的根文件系统
ltib每次执行后会在其目录下生成rootfs目录,并以其为基础生成rootfs.ext2.gz文件,而litb自带的QT库又太老,所以想到按照飞凌的<OKMX6X-S2-Qt4.8.5移植手册 ...
-
Python3基础 list insert 在指定位置挤入一个元素
Python : 3.7.0 OS : Ubuntu 18.04.1 LTS IDE : PyCharm 2018.2.4 Conda ...
-
Excel数据导入PG库,字符串正则表达式
1.Excel数据导入到PG库的某张表中:先将Excel文件转换为CSV格式,打开SQL Shell(psql),连接数据库(输入server,database,Port,username),然后再执 ...