首页 > 试题广场 >

社团主席选举

[编程题]社团主席选举

随着又一届学生的毕业，社团主席换届选举即将进行。

一共有n个投票者和m个候选人，小易知道每一个投票者的投票对象。但是，如果小易给某个投票者一些糖果，那么这个投票者就会改变他的意向，小易让他投给谁，他就会投给谁。

由于小易特别看好这些候选人中的某一个大神，这个人的编号是1，所以小易希望能尽自己的微薄之力让他当选主席，但是小易的糖果数量有限，所以请你帮他计算，最少需要花多少糖果让1号候选人当选。某个候选人可以当选的条件是他获得的票数比其他任何候选者都多。

第一行两个整数n和m，表示投票者的个数和候选人的个数。
接下来n行，每一行两个整数x和y，x表示这个投票者的投票对象，y表示需要花多少个糖果让这个人改变意向。
满足1 <= n, m <= 3000，1 <= x <= m，1 <= y <= 10⁹。

一个整数，糖果的最小花费。

示例1

输入

1 2
1 20

示例2

算法知识视频讲解

bandiaoz

发表于 2024-12-25 23:30:53

解题思路这是一道选举问题，可以用DFS（深度优先搜索）来解决。主要思路如下：对于每一步，我们都有两个选择：贿赂所有未贿赂者中需要最少糖果的人贿赂当前得票最多的候选人的支持者中需要最少糖果的人使用DFS遍历所有可能的贿赂组合，找到使1号候选人获胜所需的最少糖果数关键优化：展开全文

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师排序贪心模拟穷举网易 2019 拼多多集团-PDD Java工程师

上传者：小小

难度：

9条回答 74收藏 8480浏览

查看代码

社团主席选举

扫一扫，把题目装进口袋