现场调试有问题,没做出来,five选手,只做记录,还请多多指教
题目:n个朋友,每个人有金币x,有m个房子,每个房子有舒适度和价格,当前仅当这个人金币数大于房子价格时才能购买,每个人至多买一个房子,每个房子最多被一个人买,求最大舒适度;
输入:2 2 // 朋友数:n 房子数:m
2 2 // 朋友1的金币 朋友2的金币
2 2 // 房子1的舒适度 房子1的价格
2 2 // 房子2的舒适度 房子2的价格
输出:4 // 最大舒适度和,即每个人买一个2舒适度的房子
思路:房子按照舒适度从大到小排列,金币从小到大排列,去最小化价格差异买到最大舒适度的房子
import java.util.Arrays;
import java.util.Scanner;
//第一题:n个朋友,每个人有金币x,有m个房子,每个房子有舒适度和价格,当前仅当这个人金币数大于房子价格时才能购买,每个人至多买一个房子,每个房子最多被一个人买,求最大舒适度
public class Main{public static void main(String []args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(); //朋友数int m = sc.nextInt(); //房数int coin[] = new int[n]; //钱for (int i = 0; i < n; i++) {coin[i] = sc.nextInt();}int house[][] = new int[m][2]; //第3列用来标记是否卖出for (int i = 0; i < m; i++) {for (int j = 0; j < 2; j++) {house[i][j] = sc.nextInt();}}sortByFitness(house, 0);Arrays.sort(coin);
// for(int i = 0; i < m; i++) {
// for (int j = 0; j < 2; j++)
// System.out.print(house[i][j] + " ");
// }int sum = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (coin[j] >= house[i][1]) {sum += house[i][0];coin[j] = -1;break;}}}System.out.println(sum);}//按照第 index列 排序private static void sortByFitness(int[][] house,int index) {int row = house.length;int line = house[0].length;for (int i = 0; i < row; i++) {for (int j = i; j < row - 1; j++)if (house[j][index] < house[j + 1][index]) {int temp[] = new int[line];for (int k = 0; k < line; k++)temp[k] = house[j][k];house[j] = house[j + 1];house[j + 1] = temp;}}}
}