思路来源于bilibili 左程云,看不懂的话可以直接去看他的视频
https://www.bilibili.com/video/BV1ST4y1s7XT/?spm_id_from=333.999.0.0&vd_source=9be04b601857ae0209bebc550448d13b
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
/*
具体思路
想要知道我们需要带的最少钱数,换个角度想,就是公园怎么最挣钱,带这个钱数是绝对保证每个人能游玩
因此,我们可以计算出每个项目,多少人游玩的时候是最赚钱的,可以先将最赚钱的项目赚的钱拉满,之后再去让剩下的人去玩别的最赚钱项目
一个项目,当有x人游玩时,当前人的门票钱的计算公式如下
赚的钱=原票价 - (x + 1) * 折扣 - (x * 折扣)(这部分为一个新的人到来,之前人享受的折扣) (新人付出的门票钱)
*/
public class Main {
static class Game{
//折扣
public int ki;
//项目的原票价
public int bi;
//之前的人游玩人数
public int people;
public Game(int k,int b) {
ki = k;
bi = b;
people = 0;
}
//如果再来一个人,这个项目可以得到多少钱
public int earn() {
/*
* 例如:当bi = 10,ki = -2
* 1个人来时,赚8元 10 + (0+1)*-2 + 0 = 8 元 之前0个人游玩
* 2个人来时 赚4元 10 - 2*2 - 1*2 = 4 元 之前1个人游玩
* 3个人来时 不赚钱了,因此最多就赚12元,也代表我们带了12元就够用
*/
return bi + (people + 1) * ki + people * ki;
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] s = in.readLine().split(" ");
//参加活动的人数
int n = Integer.parseInt(s[0]);
//项目个数
int m = Integer.parseInt(s[1]);
//大根堆,按照每个项目赚的钱数排序
PriorityQueue<Game> heap = new PriorityQueue<>((a,b) -> b.earn() - a.earn());
for(int i = 0;i < m;i++) {
String[] s1 = in.readLine().split(" ");
int ki = Integer.parseInt(s1[0]);
int bi = Integer.parseInt(s1[1]);
heap.add(new Game(ki, bi));
}
//此处要注意可能爆int
long ans = 0;
//一个一个人依次送到当前最赚钱的项目里去
for(int i = 0;i < n;i++) {
//如果当前最赚钱的项目都赚不到钱了,直接跳出即可,后面的人再来这个项目也没啥意义
if(heap.peek().earn() <= 0) {
break;
}
//将最赚钱的项目拿出来
Game cur = heap.poll();
//统计赚的钱数
ans += cur.earn();
//之前的人数+1
cur.people++;
//放回堆中
heap.add(cur);
}
System.out.println(ans);
}
}
牛,看了之后豁然开朗