uq_43625241302

用户名：uq_43625241302

访问量：3158

签　名：

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

　　自我简介：

TA的其他文章

并查集 + 模拟 = 恶心
浏览：557

贪心 + 优先队列
浏览：871

模拟分类（标题不能太短）
浏览：424

你可能喜欢

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

贪心 + 优先队列

　　作者: uq_43625241302　　　　发表时间：2023-05-04 01:50:22 浏览：871　|　评论：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 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

uq_43625241302

TA的其他文章

你可能喜欢

不需要数组和指针的做法！！！

IP判断（C语言代码）

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

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

【明明的随机数】（C语言代码）

贪心 + 优先队列

评论区

精彩推荐

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

简单的a+b （C语言代码）

1051（奇了怪了）

程序员的表白（C语言代码）

分糖果（C语言代码）

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

简单的a+b （C语言代码）

简单的a+b （C语言代码）

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

字符串的修改（C语言代码）

uq_43625241302

TA的其他文章

你可能喜欢

不需要数组和指针的做法！！！

IP判断 （C语言代码）

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

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

【明明的随机数】 （C语言代码）

贪心 + 优先队列

评论区

精彩推荐

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

简单的a+b （C语言代码）

1051（奇了怪了）

程序员的表白 （C语言代码）

分糖果 （C语言代码）

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

简单的a+b （C语言代码）

简单的a+b （C语言代码）

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

字符串的修改 （C语言代码）

IP判断（C语言代码）

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

【明明的随机数】（C语言代码）

　　评论区

程序员的表白（C语言代码）

分糖果（C语言代码）

字符串的修改（C语言代码）