【笔试题】百度+美团
发工资
链接:https://www.nowcoder.com/questionTerminal/e47cffeef25d43e3b16c11c9b28ac7e8
来源:牛客网
小度新聘请了一名员工牛牛, 每个月小度需要给牛牛至少发放m元工资(给牛牛发放的工资可以等于m元或者大于m元, 不能低于m)。
小度有一些钞票资金, 一共有n种不同的面额, 对于面额为x_ix
i
的钞票, 小度有y_iy
i
张, 并且每一个钞票面额都能整除所有比它大的面额, 并且每一张钞票不能找零。
小度想知道这部分资金最多能牛牛发放多少个月的工资?
示例1
输入
3 51
100 1
50 4
1 2
输出
4
说明
注意钱不能找零,所以:
100能支付一个月工资
50+1,50+1能支付两个月工资
50+50能支付一个月工资
即最多能支付四个月的工资。
贪心
#include <bits/stdc++.h>
#include <vector>
using namespace std;
struct money{long long mon;int num;
};
bool cmp(money a, money b){return a.mon > b.mon;
}
int main() {int a;long long sum = 0, b;cin >> a >> b;money arr[a];for(int i = 0; i < a; i++){cin>>arr[i].mon>>arr[i].num;}sort(arr, arr + a, cmp);//第一种情况把大于工资的花完,先把大钱用完for(int i = 0; i < a; i++){if(arr[i].mon >= b){sum += arr[i].num;arr[i].num = 0;}else break;}//开始车轮战,每一趟while发出一个月工资while(true){long long needToPay = b;//先从大面额开始涮一轮,在不超b的情况下,尽可能地拿大面额for(int i = 0; i < a; i++){if(arr[i].num == 0) continue;//比如需要支付的工资是51,现在的面额是20,那么需要51 / 20 = 2张;并且接下来需要支付的工资变成51 - 40 = 11long long needNum = needToPay / arr[i].mon;needNum = min(needNum, (long long)arr[i].num);arr[i].num -= needNum;needToPay -= needNum * arr[i].mon;}//刚好凑成了就结束这一趟if(needToPay <= 0){sum++;continue;}//注意是倒序:再从小面额开始补(此时所有面额都已大于needToPay)for(int i = a - 1; i >= 0; i--){if(arr[i].num == 0) continue;arr[i].num--;needToPay -= arr[i].mon;sum++;break;}if(needToPay > 0) break;}cout<<sum<<endl;
}
// 64 位输出请用 printf("%lld")
摆火柴
牛牛给了小度n根火柴和m种数字(m只能是1到9),小度只能摆这m种数字,小度想知道能摆出来最大的数的多少。
如图所示: 摆数字1,2,3,4,5,6,7,8,9 分别需要花费 2,5,5,4,5,6,3,7,6根火柴。
时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 256M,其他语言512M
输入描述:
第一行两个数n,m。
第二行m个数,表示小度可以摆放的数。
输出描述:
一行表示答案。
示例1
输入例子:
20 4
3 7 8 4
输出例子:
777773
例子说明:
火柴得使用完
贪心+回溯
一种比动规好理解的回溯解法
首先需要字典映射。
当遇到选择列表的时候,可以考虑回溯。
注意先要按照题意排序,按照排序(偏贪心)的基础上,在进行回溯。
最后的结果记得在字母排序
#include<bits/stdc++.h>
using namespace std;bool backtrack(map<int,int>& mt, vector<pair<int,int>> v, string& ret, int n ){//base caseif(n==0){return true;}for(int i =0; i< v.size();i++){if(v[i].second<=n){//当前得满足剩余的火柴棍得数目ret.push_back(v[i].first+'0');bool res = backtrack(mt,v,ret,n-v[i].second);//当前字符以及对应得剩余火柴棍数if(res) return true;ret.pop_back();//回溯}}return false;
}int main(){map<int,int> nums;nums[1]=2;nums[2]=5;nums[3]=5;nums[4]=4;nums[5]=5;nums[6]=6;nums[7]=3;nums[8]=7;nums[9]=6;int n,m,x;while(cin>>n>>m){vector<pair<int,int>> v;for(int i =0; i< m;i++){cin>>x;v.push_back({x,nums[x]});//数字以及对应的火柴棍的数量}sort(v.begin(),v.end(),[](pair<int,int> a, pair<int,int> b){if(a.second!=b.second){return a.second< b.second;//火柴棍少的放在前面}else{return a.first>b.first; //数字大的放前面}});string res="";//回溯,来找在满足排序条件下最终能组成得字符串backtrack(nums,v,res,n);//当前字符以及对应得剩余火柴棍数sort(res.begin(),res.end(),[](char a, char b){return a>b;//确保数字从大到小排序,这样得到的就是最大得数字});cout<<res<<endl;}return 0;
}
神秘的苹果树
链接:https://www.nowcoder.com/questionTerminal/3f060b099d604ec3875d8826a69a4561
来源:牛客网
小团找到一颗有n个节点的苹果树,以1号节点为根,且每个节点都有一个苹果,苹果都有一个颜色,但是这棵树被施加了咒术,这使得小团只能从某一个节点的子树中选取某一种颜色的拿。小团想要拿到数量最多的那种颜色的所有苹果,请帮帮她。每次她会指定一个节点t,如果小团只能从节点t的子树中选取某一种颜色的苹果,选取什么颜色能拿到最多的苹果?如果有多种颜色都可以拿同样多的苹果,输出颜色编号最小的那个对应的编号。
节点x的子树定义为所有将x当作祖先的节点,x也视为x的子树的一部分。
输入描述:
第一行一个正整数n表示这颗树上节点的个数。
接下来n-1行,每行两个正整数xi,yi,表示树上第i条边连接的两个节点。
接下来一行n个正整数ci,分别表示从1~n号节点上的苹果的颜色。
接下来一行一个正整数q,表示接下来有q次独立的询问。
接下来q行,每行一个正整数t表示询问:如果小团只能从节点t的子树中选取某一种颜色的苹果,选取什么颜色能拿到最多的苹果?如果有多种颜色都可以拿同样多的苹果,输出颜色编号最小的那个对应的编号。
对于100%的数据n≤5000, 1≤xi,yi,t≤n, ci≤1000000000,q≤1000
输出描述:
输出q行,每行一个整数,表示答案。
示例1
输入
7
1 2
1 3
2 4
2 5
3 6
3 7
1 1 2 1 2 2 3
7
1
2
3
4
5
6
7
输出
1
1
2
1
2
2
3
dfs
#include <iostream>
#include <vector>
#include <map>
using namespace std;map<int, int> process(vector<vector<int>>& edges, vector<int>& color, vector<int>& dp, int fa, int curr){map<int, int> mp;mp[color[curr]]++;for(auto c : edges[curr]){if(c == fa)continue;map<int, int> temp = process(edges, color, dp, curr, c);for(auto it : temp){mp[it.first] += it.second;}}int maxVal = 0, colorId = -1;for(auto it : mp){if(maxVal < it.second){maxVal = max(maxVal, it.second);colorId = it.first;}}dp[curr] = colorId;return mp;
}int main(){int n;cin >> n;vector<vector<int>> edges(n+1);for(int i = 0; i < n-1; i++){int x, y;cin >> x >> y;edges[x].push_back(y);edges[y].push_back(x);}vector<int> color(n+1);for(int i = 1; i <= n; i++){cin >> color[i];}vector<int> dp(n+1, 0);process(edges, color, dp, 0, 1);int q;cin >> q;while(q--){int t;cin >> t;cout << dp[t] << endl;}return 0;
}
相关文章:
【笔试题】百度+美团
发工资 链接:https://www.nowcoder.com/questionTerminal/e47cffeef25d43e3b16c11c9b28ac7e8 来源:牛客网 小度新聘请了一名员工牛牛, 每个月小度需要给牛牛至少发放m元工资(给牛牛发放的工资可以等于m元或者大于m元, 不能低于m)。 小度有一些钞票资金…...

【8.索引篇】
索引分类 索引和数据就是位于存储引擎中: 按「数据结构」分类:Btree索引、Hash索引、Full-text索引。按「物理存储」分类:聚簇索引(主键索引)、二级索引(辅助索引)。按「字段特性」分类&#…...

MySQL InnoDB存储引擎锁与事务实现原理解析(未完成)
InnoDB MySQL存储引擎是基于表的,也就是说每张表可以选择不同的存储引擎。 InnoDB存储引擎的表是索引组织的,也就是数据即索引。 存储引擎文件 InnoDB引擎会包含RedoLog重做日志文件和TableSpace表空间文件。 表空间文件 默认表空间文件(…...
P1683 入门(洛谷)JAVA
题目描述: 不是任何人都可以进入桃花岛的,黄药师最讨厌像郭靖一样呆头呆脑的人。所以,他在桃花岛的唯一入口处修了一条小路,这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩,我们认为是安全的,而有的瓷砖…...

yocto编译烧录和脚本解析
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录前言一、初始化构建目录二、imx-setup-release.sh脚本解析三、编译单独编译内核四、烧录总结前言 本篇文章主要讲解如何在下载好源码之后进行编译和yocto的脚本解析…...
Proteus 8.15安装包安装教程
Proteus介绍Proteus的介绍Proteus8.15安装包Proteus8.15安装教程Proteus的介绍 Proteus是英国著名的EDA工具(仿真软件),从原理图布图、代码调试到单片机与外围电路协同仿真,一键切换到PCB设计,真正实现了从概念到产品的完整设计。是世界上唯…...

Spring——AOP工作流程
AOP就是代理模式的开发简化 1.Spring容器启动 因为AOP是要将通知类作为一个bean对象交给spring进行管理的,还有经过通知类被增强的类。 此时还没有创建bean对象 2.读取所有切面配置中的切入点 在下面这段代码中,定义了两个切入点,但是只…...
c++11多线程之condition_variable、wait()、notify_one()、notify_all()的使用。
系列文章目录 文章目录系列文章目录前言一、基本概念1.1 std::condition_variable1.2 wait()函数1.2.1 wait()带第二个参数1.2.2 wait()不带第二个参数1.2.3 当其他线程用notify_one()或notify_all()1.3 notify函数二、代码实例总结前言 C11多线程&…...
skywalking扩展实现 —— 监控数据的动态上报
把标题名整高大上一些,来掩盖需求的奇葩。 0. 目录1. 需求背景2. 需求描述3. 优势4. 实现4.1 扩展点4.2 配置项5. 优化6. 提醒7. 补充 - 关于微服务8. 参考1. 需求背景 过去一段时间,接手了一个迭代了数年的"基于微服务架构"搭建的产品。 自…...
【GoF 23】23种设计模式与OOP七大原则概述
1. 什么是GoF 23? GoF 23也就是23种设计模式。1995年GoF(Gang of Four,四人组/四人帮)合作出版了《设计模式:可复用面向对象软件的基础》一书,一共收录了23种设计模式,从此梳理了软件设计模式领…...
Java 日期时间
Java 日期时间是 Java 标准库中一个非常重要的部分,它提供了丰富的 API 来处理日期、时间以及日期时间。在 Java 应用程序中,我们经常需要处理日期时间相关的操作,例如计算两个日期之间的差、将日期时间转换为不同的时区等。在本篇文章中&…...

Face Forgery Suvery
文章目录Face ForgeryFace Forgery classAttribute ManipulationExpression SwapIdentity SwapEntire Face SynthesisFace Forgery DetectionLow-levelOn the Detection of Digital Face Manipulation(CVPR2020)High-levelProtecting World Leaders Against Deep FakesDetectin…...

案例学习--016 消息队列作用和意义
简介MQ全称为Message Queue, 是一种分布式应用程序的的通信方法,它是消费-生产者模型的一个典型的代表,producer往消息队列中不断写入消息,而另一端consumer则可以读取或者订阅队列中的消息。主要产品有:ActiveMQ、RocketMQ、Rabb…...

【MySQL】MySQL的锁机制
目录 概述 MyISAM 表锁 InnoDB行锁 概述 锁是计算机协调多个进程或线程并发访问某一资源的机制(避免争抢)。 在数据库中,除传统的 计算资源(如 CPU、RAM、I/O 等)的争用以外,数据也是一种供许多用户共…...
HTML 背景
一个富有美感的背景会让站点看上去更加高级、更有吸引力。本篇为大家来的是 HTML 背景相关内容。 背景(Backgrounds) <body> 拥有两个配置背景的标签。背景可以是颜色或者图像。 背景颜色(Bgcolor) 背景颜色属性将背景设…...
Lombok
文章目录简介原理安装常用Getter、SetterToStringEqualsAndHashCodeNonNullNoArgsConstructor、RequiredArgsConstructor、AllArgsConstructorDATABuilderLogvalCleanup简介 Project Lombok is a java library that automatically plugs into your editor and build tools, spi…...

Koa源码学习
前言 koa是一个非常流行的Node.js http框架。本文我们来学习下它的使用和相关源码 来自官网的介绍: Koa 是一个新的 web 框架,由 Express 幕后的原班人马打造, 致力于成为 web 应用和 API 开发领域中的一个更小、更富有表现力、更健壮的基石。…...
一种延迟加载自定义元素的方法
您可能实际上并不需要所有这些;通常有一个更简单的方法。如果有意使用,此处显示的技术可能仍然对您的工具集有用。 为了保持一致性,我们希望我们的自动加载器也成为一个自定义元素——这也意味着我们可以通过 HTML 轻松配置它。但首先&#…...
Pytho经典面试题荟萃:第一期
目录 一、面试题 二、参考答案 解释器和编译器的区别 解释器 编译器 Python 的解释过程 Python 内存管理 Python 内存分配 引用计数 垃圾回收 其他内存管理技术 多重继承 多重继承带来的问题 命名冲突 菱形继承问题 解决多重继承带来的问题 方法重写 调用 su…...

01背包问题(大彻大悟版)
背包问题身为一个非常经典的动态规划问题,理清思路很重要,在经过多次观看y总视频和b站解析,加上CSDN的文章辅助,我终于从很多不理解到大彻大悟,下面是我对于背包问题思路的总结,有问题的话欢迎指出。谈到背…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...

页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...