AcWing 5404. 最大开支
原题链接
困难
作者:
fourth_nt
,
2024-04-05 22:38:09
,
所有人可见
,
阅读 21
使用优先队列
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
//1.游乐园赚的最多的情况就是需要带的钱,这样无论如何选择都够支付
//2.优先选择能赚最多的项目,然后依次加人进去,看需要加多少钱,直到这个项目不再赚钱
//3.换下一个赚钱的项目,直到所有人都选择项目/所有项目都被选择完
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();
PriorityQueue<Game> games = new PriorityQueue<Game>();
for(int i = 0; i < m; i++) {
Game tGame = new Game(scanner.nextInt(), scanner.nextInt());
games.add(tGame);
}
long res = 0;
for(int i = 0; i < n; i++) {
if(games.peek().earn() <= 0)
break;
Game nowGame = games.poll();
res += nowGame.earn();
nowGame.people++;
games.add(nowGame);
}
System.out.print(res);
}
public static class Game implements Comparable<Game>{
int k; //折扣系数(负数)
int b; //原价
int people; //已经来了多少人
public Game(int k, int b) {
this.k = k;
this.b = b;
people = 0;
}
public int earn() {
return b + (people + 1) * k + people * k;
}
@Override
public int compareTo(Game o) {
return o.earn() - this.earn();
}
}
}
使用数组(会超时)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
//1.游乐园赚的最多的情况就是需要带的钱,这样无论如何选择都够支付
//2.优先选择能赚最多的项目,然后依次加人进去,看需要加多少钱,直到这个项目不再赚钱
//3.换下一个赚钱的项目,直到所有人都选择项目/所有项目都被选择完
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();
Game[] games = new Game[m];
for(int i = 0; i < m; i++) {
games[i] = new Game(scanner.nextInt(), scanner.nextInt());
}
Arrays.sort(games);
long res = 0;
for(int i = 0; i < n; i++) {
if(games[m - 1].earn() <= 0) {
break;
}
Game tGame = games[m - 1];
res += tGame.earn();
tGame.people++;
//再对数组进行排序,以保证每次都选择到最大的
Arrays.sort(games);
}
System.out.print(res);
}
public static class Game implements Comparable<Game>{
int k; //折扣系数(负数)
int b; //原价
int people; //已经来了多少人
public Game(int k, int b) {
this.k = k;
this.b = b;
people = 0;
}
public int earn() {
return b + (people + 1) * k + people * k;
}
@Override
public int compareTo(Game o) {
return this.earn() - o.earn();
}
}
}