一袋水果，给了每个水果的重量。
K次查询，每次查询给出一个s，问是否满足所有水果的重量等于s；
每次查询独立。
若不满足条件，可以从以下两个策略选择：
1 把所有重量超过平均数的水果扔掉；
2 把所有重量小于等于平均数的水果扔掉；
问是否可以通过执行若干次策略使条件满足。
这道题的难点在于k的范围<=10^5;
水果的数量也是这个范围
我的傻瓜策略就是迭代，当前重量如果大于s，就执行策略1；否则策略2；
这个方法肯定是错误的，比如 6 5 5 1 2，我要拿2，但结果只剩了1，所以不对。
显然傻瓜策略的时间复杂度会爆掉。
但至少会有一些样例通过，但测评的结果显示时间复杂度太高，显然是这个思路错了，有没有大佬说说看……
全部评论
(0) 回帖