贝壳5//8笔试最后一题

一袋水果,给了每个水果的重量。
K次查询,每次查询给出一个s,问是否满足所有水果的重量等于s;
每次查询独立。
若不满足条件,可以从以下两个策略选择:
1 把所有重量超过平均数的水果扔掉;
2 把所有重量小于等于平均数的水果扔掉;
问是否可以通过执行若干次策略使条件满足。

这道题的难点在于k的范围<=10^5;
水果的数量也是这个范围

我的傻瓜策略就是迭代,当前重量如果大于s,就执行策略1;否则策略2;
这个方法肯定是错误的,比如 6 5 5 1 2,我要拿2,但结果只剩了1,所以不对。
显然傻瓜策略的时间复杂度会爆掉。

但至少会有一些样例通过,但测评的结果显示时间复杂度太高,显然是这个思路错了,有没有大佬说说看……

#贝壳找房##笔经#
全部评论

相关推荐

努力学习的小绵羊:我反倒觉得这种挺好的,给不到我想要的就别浪费大家时间了
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
1
分享
牛客网
牛客企业服务