贪心 + 优先队列

1177 阅读 0 评论 1 点赞

原题链接：蓝桥杯2023年第十四届省赛真题-最大开支

# 贪心 + 优先队列

## 解题思路
> 问题一：某一娱乐项目所需要支付的钱随着购买人数的增加是一个怎样的趋势？

可以发现，单价为$$one = k \times x + b$$，购买人数是 x，因此所需支付的钱$$y(x) = k \times x^2 + b \times x $$。它是一个开口向下的二次函数，因此趋势是先增后减，最大值$$max = b / (- 2 \times k)$$或 $$max = b / (- 2 \times k) + 1$$。因为可以有人不选，所以**选择当前项目的人数一定是小于等于max的**

> 问题二：应该怎么选？或者说怎么选能保证每次都最优？

假设当前选的项目是第i个项目，则此时答案将增加$$incr = y_i(x + 1) - y_i(x)$$，那么我们只要保证每次选择$$incr$$最大的，即可获得正确答案。具体可用反证法进行证明。

> 问题三：如何每次获取incr最大的元素呢？

可以借助一个大根堆，将其按incr进行排序，每次获取堆顶元素。这个大根堆可以用PriorityQueue实现

## 代码实现
```
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        new Main().go();
    }

private int[][] f;
    private int[] xMax;

private PriorityQueue<int[]> pq;
    public void go() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        f = new int[m][2];
        for(int i = 0; i < m; i++) {
            f[i][0] = sc.nextInt();
            f[i][1] = sc.nextInt();
        }
		
		// 获取每个项目花钱最多的最大人数
        xMax = new int[m];
        for(int i = 0; i < m; i++) {
            xMax[i] = getMaxX(f[i][0], f[i][1]);
        }

pq = new PriorityQueue<>((a, b) -> (int) (getY(b[0], b[1] + 1) - getY(b[0], b[1]) - (getY(a[0], a[1] + 1) - getY(a[0], a[1]))));
        for(int i = 0; i < m; i++) {
            pq.offer(new int[]{i, 0});
        }

long res = 0;
        for(int i = 0; i < n; i++) {
            if(pq.isEmpty()) break;
            int[] node = pq.poll();
			// 如果当前人数在xMax的左边，则还有钱要花
            if(++node[1] <= xMax[node[0]]) {
                res += getY(node[0], node[1]) - getY(node[0], node[1] - 1);
                if(node[1] < xMax[node[0]]) pq.offer(node);
            } else break;
        }
        System.out.println(res);
    }

public int getMaxX(int k, int b) {
        int x = b / (-2 * k);
        return (long)k * x * x + (long) b * x >= (long) k * (x + 1) * (x + 1) + (long) b * (x + 1) ? x : x + 1;
    }

public long getY(int i, int x) {
        return ((long) f[i][0] * x + f[i][1]) * x;
    }
}
```

0.0分

7 人评分

本文分类：题解列表
浏览次数：1177 次浏览
发布日期：2023-05-04 01:50:22
本文链接：https://blog.dotcpp.com/a/96271

上一篇 > 1671:小九九（c++）双循环+if语句
下一篇 > 难度比蛇形矩阵简单多了

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

贪心 + 优先队列

评论列表共有 0 条评论

发表评论取消回复

贪心 + 优先队列

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复