2020年腾讯实习生算法笔试题目年腾讯实习生算法笔试题目(感触良多感触良多)
2020年腾讯实习生算法笔试题目年腾讯实习生算法笔试题目题目描述代码示例题目描述代码示例题目描述代码示例快速幂求解代码示例题目描述代码示
例题目描述代码示例
参加了腾讯20年的实习生笔试,本来都不打算写这种笔试的题目。但是感觉着产生的想法很多。首先声明我不是什么大
佬,下面写的内容没有得到印证的地方还是会出现偏差,希望各位指正。这里就先谈谈感想,如果笔试编程存在多个题目,而
这里有的部分题目不是一下做出来,那么这场笔试就已经变成了多目标优化,而事实是往往很难找到最优点,不知道如何分配
时间使你的收益最大化。所以事实就是,往往的结果不是你的收益最大化。
也许你的坚持浪费在了不该有的题目上,也许再努力一步就会有结果的题目,你却提前终止,所以结果不重要,没必要为
了不是最优的结果而悔恨。下面看题目。
题目描述题目描述
有一个人需要去打怪物,每打一个怪物需要耗费xix_ixi的血量,但是会获得yiy_iyi的金币,然后开局可以使用金币去购买血
量,一个金币可以购买qqq点血量,用不完的血量所有怪物结束之后不会保留,每一个怪物都可以选择打或者不打,问最后结
束时,可以获得最大的收益是多少。
输入描述
第一行输入n qn\ qn q,分别表示总共有n个怪物,和一个金币可以购买q点血量
接下来的n行,分别是xi yix_i\ y_ixi yi分别是打一个怪物的消耗和金币收益
输入
3 2
1 1
1 10
3 1
输出
10
这个题目应该算是比较简单的一道了,如果能正确的搞清数据的关系,直接贪心算法就可以了。如果收益大于消耗就一定
去打这个怪物,但是收益和消耗需要置换到同一维度,显然以血量为单位比较合适,只需要乘法。计算打一个怪物,收益的血
量大于消耗的血量,打完之后,金币收益累加,消耗血量累加,最后决定买多少血量即可。
因为我的描述有提出关键信息,这一题很简单,但是有很多人因为理解错题意做错了,在考场上,这种情况比比皆是。下
面看代码。
代码示例代码示例
from math import ceil
n,q= [int(i) for i in input().split(' ')] res = 0
b = 0
for i in range(n):
cost,gain = [int(i) for i in input().split(' ')] if gain *q >cost:
res += gain
b += cost
print(res - ceil(b/q))
题目描述题目描述
求函数y2=2Axy^2=2Axy2=2Ax和y=Bx+Cy=Bx+Cy=Bx+C两个曲线所围出的面积。如果没有所围面积,则输出0
输入描述
第一行一个数n,表示测试用例的组数
接下来n行,每行输入三个数,分别是A B CA\ B\ CA B C
每个用例输出一个数,表示面积,相对误差在10−410^{-4}10−4都算对
输入
1
1 1 -6
输出
31.2481110540(大概是这样,反正这样是对的)
每一个学过高等数学的同学都知道这个题要用定积分处理,所以肯定是先求交点,可能没有交点,此时所围面积就是0
了。第一个函数是yyy的二次函数,看起来不方便,把x和y交换,然后联立方程求交点。y=x22A=x−CBy=rac{x^2}
{2A}=rac{x-C}{B}y=2Ax2=Bx−C,就能得到二次函数,最后化简得到判别式>0则两个交点,存在面积,否则不存在面积。
到求交点都没什么问题,但是后面的操作就有点让我觉得自己是个憨憨。学过数值分析的同学肯定就知道计算机怎么求积
分,把一个函数切分成很多矩形或者梯形,然后把矩形(梯形)的面积累加。对了我就这样写了,不超时才怪。
正经求法应该是要对这个二次函数手动求定积分,求出来是个三次函数,然后带入上下限进行计算,别人是这样过了的。
具体细节就不展开了,直接上代码了。
评论0