2025 华子笔试(4.16)

没做,从网上看了下题面,感觉很有意思

以及t1是假题吧,最优区间覆盖不是np hard吗?

这里贴一下T3的题解:

【前置知识:经典区间调度问题】

首先第一眼过去似乎是个比较典的区间调度,按照右端点排序后贪心,但显然这个做法可以被轻易hack掉——它无法满足占有ip最少。

n=1000,那么考虑n2做法:
vector  res;
对所有区间按照右端点升序排序;
work[i].id表示业务id,work[i].num第i个业务要占有多少ip;
第一层循环i:1-n
第二层循环表示自此开始进行普通区间调度贪心选取(按右端点)。

举个例子:
i=1的时候,能完成10个业务,占用20个ip;
i=2的时候,能完成10个业务,占用18个ip;
i=3的时候只能完成9个业务,那么再往后能完成的业务数量肯定会越来越少。
我们此时应该选取i=2对应的区间,将其加入到答案中,res.push_back(work[2].id);

选取完2之后,
i=3和2冲突,跳过;
i=4的时候,能完成8个业务,占用14个ip;
i=5的时候,能完成8个业务,占用17个ip;
i=6的时候,能完成7个业务;
那么把i=4加入到答案中。

以此类推。

注意,若业务完成数量和占用ip数量都相等,需要比较一下左端点。

所以实际上只需要在经典区间调度外面加一层枚举起点即可。

end

若有错误欢迎指正

题面已经附图
#华为机试# #实习# #华为#
全部评论
第一题确实假了,说是原题i,j<=20能枚举子集,那样才能做,但是居然给t1的贪心放过去了不知是什么考量
点赞 回复 分享
发布于 04-17 11:35 陕西

相关推荐

昨天给一个大四的同学做简历修改咨询。她说自己去年秋招投了快一百个职位了,才收到3个面试邀请,所以来咨询我是不是简历写得有什么问题。我看了她的简历,确实有一些需要优化的地方。但我也和她分享了关于应届生招聘的一些真实情况。比如,投100个职位拿到3个面试机会很正常,不用觉得是自己不行。比如,求职,特别是应届生求职是一个很漫长的过程,很有可能到毕业前几天你都还在找工作。所以要管理好自己的精力,做好打持久仗的准备。比如,大规模的校招当然要参与,但也别放弃社招的途径。很多公司今年没有预算搞大规模校招,但不代表他们就不招应届生了,一些零星的适合应届生的初级岗位会通过社招渠道放出来,多尝试,别错过。我想起自己大四那年,9-12月份的秋招没有拿到任何offer。当时我做了一个投递申请记录表,差不多都已经投了快三百个岗位了,但就是颗粒无收。那个时候真的很绝望,特别是看到身边的同学们一个个都拿到满意的offer了,觉得自己真的差劲极了。我很清楚地记得12月底的一天下午,我去自习教室继续做网申、投简历,那天下了好大的雨,我的鞋子和裤子的下半截都湿了。但当傍晚我走出教学楼的时候,雨已经停了,一抬头,我看到了天边美丽的彩虹。也不知道为什么,那个时候我突然觉得自己的求职之路肯定很快也会雨过天晴。后来又过了一两周,我从社招途径拿到一个offer,是一个实习生可以转正的工作机会。于是我就去了那家公司实习,毕业以后也留在了这家公司开始了我的第一份正式工作。我们总是很容易注意到别人的成功,但不容易发现(或者也没有机会了解)在成功之前,TA可能已经经历了无数次的失败。我不知道自己的这段经历能不能安慰到现在正在为找工作焦虑不安的应届生朋友们。但是,真的,在求职这件事上,失败是一种常态。但最后你只要成功一次,你就成功了。所以,你要做的就是:多尝试,别放弃!#牛客激励计划# #牛客创作赏金赛# #找工作如何保持松弛感?#
点赞 评论 收藏
分享
评论
2
2
分享

创作者周榜

更多
牛客网
牛客企业服务