08-17 22:52 已编辑 电子科技大学 C++ 发布于四川
关注
米哈游笔试0817
单选
多选
1. 原神冲月卡30元立即送300，后面每天可以领30个原石。也可以直接买1元10个。问想在m天内获取n个原石。怎么冲最划算。算是签到题，直接计算即可
2. 一个路上有m个点，i号工人能给[li, ri]区间的每个点种上树，如果某个点已经种了树，那就跳过这个点。给出n个工人的种植区间，如果说想开除一个工人不影响结果，那请问能开除工人可选数。
思路:数组a存i位置多少工人能种树(遍历，根据lr边界更新工人数量即可)。数组b存储i位置对应的最右边界是多少(输入lr时候判断是否更新B[l]为r即可)。
遍历a数组，找到第一个1出现的位置为index，这个位置的工人不能解雇。然后根据b跳转到第一个大于等于index的最右边界+1，也就是这个工人的右边界，防止重复计算。最后统计出现多少1即可。只过了30%，这个思路有啥问题吗
3. 因为2卡死了，没看
多选
1. 原神冲月卡30元立即送300，后面每天可以领30个原石。也可以直接买1元10个。问想在m天内获取n个原石。怎么冲最划算。算是签到题，直接计算即可
2. 一个路上有m个点，i号工人能给[li, ri]区间的每个点种上树，如果某个点已经种了树，那就跳过这个点。给出n个工人的种植区间，如果说想开除一个工人不影响结果，那请问能开除工人可选数。
思路:数组a存i位置多少工人能种树(遍历，根据lr边界更新工人数量即可)。数组b存储i位置对应的最右边界是多少(输入lr时候判断是否更新B[l]为r即可)。
遍历a数组，找到第一个1出现的位置为index，这个位置的工人不能解雇。然后根据b跳转到第一个大于等于index的最右边界+1，也就是这个工人的右边界，防止重复计算。最后统计出现多少1即可。只过了30%，这个思路有啥问题吗
3. 因为2卡死了，没看
全部评论
牛客295871004号
The University of New South Wales Java
可以用数组放种树的个数，一次遍历种树一次遍历拔树，拔完发现没树了这个人不能删。
HHHHaos
门头沟学院 C++
第二题我是用前缀和加差分数组来做的，先求出每一个位置种的树的多少，对于其中只中了一棵树的位置求前缀和，这样就可以O（1）求区间内中了一棵树的位置的多少，然后如果这个区间内有种了一棵树的那就不能解雇
我真的不想面试啊 楼主
楼主 电子科技大学 C++
难受😣
艾义
大阪大学 算法工程师
同做复杂了 一直在优化区间合并
摩拉克斯_
武汉大学 Java
第一题二分法，第二题先做查分数组，再把大于1位置的元素变为0，在计算前缀和数组就行了，
我真的不想面试啊 楼主
楼主 电子科技大学 C++
有个bug，没考虑到l和r相等情况，跳转时候应该跳转到本工人的右边界，不应该是第一个大于index的右边界值，应该是第一个大于等于index的右边界值。╯﹏╰
相关推荐
查看25道真题和解析
