uq_43625241302

用户名：uq_43625241302

访问量：2885

签　名：

等　　级
排　　名	7389
经　　验	1259
参赛次数	1
文章发表	6
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

预处理 + 双端队列
浏览：298

你可能喜欢

贪心 + 优先队列

　　作者: uq_43625241302　　　　发表时间：2023-05-04 01:50:22 浏览：806　|　评论：0　

原题链接：蓝桥杯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分

12 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

uq_43625241302

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C++代码）

简单编码（C++代码）（这里推荐用switch）

汽水瓶（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

贪心 + 优先队列

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

母牛的故事（C语言代码）

C语言训练-求函数值（C语言代码）

WU-输入输出格式练习（C++代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

uq_43625241302

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C++代码）

简单编码 （C++代码）（这里推荐用switch）

汽水瓶 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

贪心 + 优先队列

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

母牛的故事 （C语言代码）

C语言训练-求函数值 （C语言代码）

WU-输入输出格式练习 （C++代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

简单编码（C++代码）（这里推荐用switch）

汽水瓶（C语言代码）

　　评论区

母牛的故事（C语言代码）

C语言训练-求函数值（C语言代码）

WU-输入输出格式练习（C++代码）