贪心 + 优先队列

解题思路

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

可以发现，单价为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;
    }
}