今天的题相比之前不是太难，第一题贪心用优先队列优化，第二题类似最长上升子序列。
第一题：
有n个人，每人有对应的钱币，有m个房子，每个房子有对应的价值和舒适度。
每个人只能买一个房子，每个房子只能被一个人买，求最大的舒适度和。
解法：
贪心，首先对每个人拥有的钱币大小排序，再对房子按价格大小排序。
每个人买他能买到的价格内最大舒适度的房子，总和即为所求。
public class Ali {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
int[] money = new int[n]; // 每个人的金币
for (int i = 0; i < n; i ++)
money[i] = sc.nextInt();
// 第一个维度是舒适度，第二个维度是价格
int[][] house = new int[m][2];
for (int i = 0; i < m; i++) {
house[i][0] = sc.nextInt();
house[i][1] = sc.nextInt();
}
Arrays.sort(house, (o1, o2) -> o1[1] - o2[1]); //house按价格排序
Arrays.sort(money); // 钱少的人先选
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1); //用优先队列进行优化
long res = 0; //这题要用long, 给的都是大数
int index = 0;
for (int i = 0; i < money.length; i ++){
int cur_money = money[i];
while (index < house.length && house[index][1] <= cur_money){
queue.add(house[index][0]);
index ++;
} //把当前能买的所有房子放进去
int add = 0;
if (!queue.isEmpty()){
add = queue.poll(); //得到能买的房子中最大舒适度的房子
}
res += add;
}
System.out.println(res);
}
}
第二题：
给定一个字符串，字符串只包含abcdef 6个字母，求满足下列规则的最长子序列：
1.a必须在c,e前，c必须在e前；
2.b必须在d,f前, d必须在f前;
解法：
两个条件相互独立，可以首先把输入字符串拆分成两个只包含ace的字符串和bdf的字符串
然后求每个字符串的最长不下降子序列，和即为所求。
最长不下降子序列的求法应用二分优化，不会的可以看看leetcode最长上升子序列的解法。
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[] cs = sc.next().toCharArray();
int len = cs.length;
int l1 = 0, l2 = 0;
char[] c1 = new char[len];
char[] c2 = new char[len];
for (char c : cs) {
if (c == 'a' || c == 'c' || c == 'e') c1[l1++] = c;
if (c == 'b' || c == 'd' || c == 'f') c2[l2++] = c;
}
System.out.println(LIS(c1, l1) + LIS(c2, l2));
}
public static int LIS(char[] arr, int len) {
int[] dp = new int[arr.length];
int res = 0;
for (int i = 0; i < len; i++) {
char num = arr[i];
int l = 0, r = res;
while (l < r) {
int m = (l + r) / 2;
if (dp[m] <= num) l = m + 1;
else r = m;
}
dp[l] = num;
if (l == res) res++;
}
return res;
}
}
全部评论
(13) 回帖