题解：P12331 [蓝桥杯 2023 省 Java B] 最大开支

_Null_Ptr · 2025-04-25 20:38:44 · 题解

蓝桥杯2023省赛Java B组「最大开支」题解

本题的关键在于每次分配人员时，选择能使‌边际收益‌最大的项目（边际收益指的是当前项目增加一人带来的花费增量）。

由题意得，对于项目 i，当已有 x_i 人时：

• 当前总花费：k_ix_i^{2} + b_ix_i

• 增加一人后的总花费：k_i\times(x_i+1)^{2} + b_i\times(x_i+1)

• 边际收益：[k_i\times(x_i+1)^{2} + b_i\times(x_i+1)] - (k_ix_i^{2} + b_ix_i) = k_i\times(2x_i + 1) + b_i

故可以使用‌最大堆‌来动态维护各项目的边际收益，每次取出边际收益最大的项目进行分配，然后更新该项目的边际收益。

下面贴上代码，注意看数据范围，记得开 long long。

#include <iostream>
#include <queue>
#define int long long 
using namespace std;
struct p {
    int k,b,x,ic;
    bool operator<(const p& other) const {return ic < other.ic; }
}; 
priority_queue<p> pq;
int n, m, k, b, anss;
main() {
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        cin >> k >> b;
        int icc = k+b;
        if (icc>0) pq.push({k, b, 0, icc});
    }
    int rm=n;
    while (rm>0&&!pq.empty()) {
        p curr = pq.top();
        pq.pop();
        anss += curr.ic;rm--;
        int new_x = curr.x + 1,newi=curr.k*(2*new_x+1)+curr.b;
        if (newi > 0) pq.push({curr.k,curr.b,new_x,newi});
    }

    cout<<anss<<endl;
}

import java.util.PriorityQueue;
import java.util.Scanner;

class P implements Comparable<P> {
    long k;
    long b;
    long x;
    long ic;

    public P(long k, long b, long x, long ic) {
        this.k = k;
        this.b = b;
        this.x = x;
        this.ic = ic;
    }

    @Override
    public int compareTo(P other) {
        return Long.compare(other.ic, this.ic);
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long m = scanner.nextLong();

        PriorityQueue<P> pq = new PriorityQueue<>();
        long anss = 0;

        for (int i = 1; i <= m; i++) {
            long k = scanner.nextLong();
            long b = scanner.nextLong();
            long icc = k + b;
            if (icc > 0) {
                pq.add(new P(k, b, 0, icc));
            }
        }

        long rm = n;
        while (rm > 0 && !pq.isEmpty()) {
            P curr = pq.poll();
            anss += curr.ic;
            rm--;
            long new_x = curr.x + 1;
            long newi = curr.k * (2 * new_x + 1) + curr.b;
            if (newi > 0) {
                pq.add(new P(curr.k, curr.b, new_x, newi));
            }
        }

        System.out.println(anss);
        scanner.close();
    }
}