这是一道不错的思维题,也是贪心题,可用三分,也可以不用.
选举在即,有N个人,M个党派.但是可以花钱让某个人改变投票,自己的党派为1,最少花多少钱可以使自己赢得选举(1的票数分别严格大于所有其他党派的票数)?
这道题一拿到手没什么思路啊,感觉是Greedy(贪心),但是又想不出什么好策略,没办法从局部最优推向全局最优.
思路就是枚举一个k表示阈值,使得1的票数大于等于k,所有其他党派票数都严格小于k,由此计算一个cost,再取最小cost即可.
计算cost的方法是:将人们的投票情况根据价格排序,然后从小到大枚举,如果当前这个人投的党派不是党派1且票数大于等于k,那么这个人的想法就应该改变,就收买他,并给他打上标记.最后再遍历一遍,确保1的票数大于等于k,注意打上标记的表示这个人已经收买,不能再收买.最后将收买所需价格返回即可.
你以为这样就结束了?在枚举的过程中发现,这个cost具有单调性,随k增大,先减后增,所以可以用三分求到最小值.于是乎,将原本的遍历k改成三分就行了.复杂度O(N * logN),耗时15ms.