51nod 1494 选举拉票【贪心】【扫描线】【线段树】2023华为od机试真题【人气最高的店铺】

51nod 1494 选举拉票和华为od机试真题【人气最高的店铺】,这两题的思路是一样的,所以放在一起分析.原题在最下面.

题解:

线段树的专题请自行了解,目的是为了性能,快速得到前K小的值.不在乎性能可以用优先队列,然后截取前K值求和即可.不影响我们的思路.至于扫描线,我也没有具现出来,所以不解析.

按题意.我们假设作为县长,首先获取所有选民的票数,总花费sum元,得到所有的选票n(包括投给自己和对手的票),然后逐步把选票还给原先对手.具体实现,先对对手的选票进行代价从高到低排序,如示例中:1 2,1 2,1 2,2 1,0 0.解析求得1号对手有[2,2,2],2号对手有[1],自己不算.我们再分为代价rank组,rank[1]=[2,1],rank[2] =[2],rank[3]=[2].这里的含义就是当我们把rank[1]的票退回给对手,这时对手(1,2)手上至多有1票,这时只要我们县长手上的票比1大,则成立我们具有最多的票.再把rank[2]退回,那么对手(1)手上至多有2票,而我们这时如果不够3票,那么就要从退回的票中选择差值个k票,取前k小代价的.如此类推,当我们把rank都退回,示例中,我们只有1票,而对手有3票,所以我们从选票中选取  3-1+1 =3(k)票,加1是为了比3大.枚举所有对手可能拥有的票,而不是我们所有的票,只要比对手多一票即可.

核心代码

     // n是总票数,ans是已统计出的所以选择的代码总和
      let c = n, sum = ans;
     // i的循环次数,是对手最大的选票次数.所以这里可以优化,只要循环rank的范围即可
     for (let i = 1; i <= n; i++) {
        // 表示手上的票
        c -= b[i].length;
        // 把票退回给对手
        for (let j = 0; j < b[i].length; j++) {
 
            // 这里换成优先队列,下面取前k的值和即可.
 
            change(1, 1, m, b[i][j]);
 
            // 表示手上的票花费的金额
 
            sum -= b[i][j]  
 
        }
 
        let t = 0;
        /*
i是选手最多的票数.所以c<=i,即是自己的选票最多与i相同,后面即从众多的选票中抽取差值k(i - c + 1)小,加1是为了比对手多一票.
*/