Alice 和 Bob 在班级内竞选班长。班级中有 � N ( 1 ≤ � ≤ 2 × 1 0 5 ) (1≤N≤2×10 5 ) 个小组,第 � i 个小组有 � � A i 个同学想选 Alice 为班长,剩下的 � � B i 个同学不想做出决定。 ( 1 ≤ � � , � � ≤ 1 0 9 ) (1≤A i ,B i ≤10 9 ) Bob 能在各个小组内举行演讲。 如果 Bob 在一个小组内做了演讲,那么该小组的所有同学(一共 � � + � � A i +B i 个)将会全部给 Bob 投票。 如果 Bob 在一个小组内没有做演讲,那么该小组的 � � A i 个同学会给 Alice 投票,剩下的 � � B i 个同学不会给 Bob 投票。 Bob 想比 Alice 获得更多投票,他至少需要在多少个小组内做演讲呢?
时间: 2023-04-02 07:02:52 浏览: 216
班级选举系统
这是一个算法问题,我可以回答。Bob 至少需要在 ceil((sum(Ai)-sum(Bi))/2) 个小组内做演讲,其中 sum(Ai) 表示所有小组中想选 Alice 为班长的同学总数,sum(Bi) 表示所有小组中不想做出决定的同学总数。
阅读全文