uq_43625241302

用户名：uq_43625241302

访问量：391

签　名：

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

　　自我简介：

TA的其他文章

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

贪心 + 优先队列
浏览：137

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

你可能喜欢

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

贪心 + 优先队列

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

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

# 贪心 + 优先队列

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

可以发现，单价为$$one = k \times x + b$$，购买人数是 x，因此所需支付的钱$$y(x) = k \times x^2 + b \times x $$。它是一个开口向下的二次函数，因此趋势是先增后减，最大值$$max = b / (- 2 * k)$$或 $$max = b / (- 2 * 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分

4 人评分

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

uq_43625241302

TA的其他文章

你可能喜欢

分糖果（C++代码）

C语言训练-尼科彻斯定理（C语言代码）。。。内含证明定理

C语言训练-谁家孩子跑最慢* （C语言代码）

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

点我有惊喜！你懂得！

贪心 + 优先队列

评论区

精彩推荐

C语言训练-求素数问题（C语言代码）

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

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

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

C语言训练-数字母（C语言代码）

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

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

输出九九乘法表（C语言代码）

整数平均值（C语言代码）

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

uq_43625241302

TA的其他文章

你可能喜欢

分糖果 （C++代码）

C语言训练-尼科彻斯定理 （C语言代码）。。。内含证明定理

C语言训练-谁家孩子跑最慢* （C语言代码）

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

点我有惊喜！你懂得！

贪心 + 优先队列

评论区

精彩推荐

C语言训练-求素数问题 （C语言代码）

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

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

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

C语言训练-数字母 （C语言代码）

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

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

输出九九乘法表 （C语言代码）

整数平均值 （C语言代码）

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

分糖果（C++代码）

C语言训练-尼科彻斯定理（C语言代码）。。。内含证明定理

　　评论区

C语言训练-求素数问题（C语言代码）

C语言训练-数字母（C语言代码）

输出九九乘法表（C语言代码）

整数平均值（C语言代码）