首页 > 贝壳5//8笔试最后一题
头像
讨厌做饭
发布于 2021-05-08 21:50
+ 关注

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

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

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

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

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

全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐