前言
"──妳在意他吗？"
"呀啊！"
珂朵莉被人突然从后面抱住，发出了奇怪尖叫声。
"哦──反应不赖。"
"欸，不……不要吓我啦！"
"喵哈哈，抱歉抱歉。谁教妳从刚才就一动也不动，让人看了忍不住──"
"那算什么理由嘛，真是的。" 珂朵莉把绕到她脖子上的手甩开。
整体评价
t3枚举+二分找上下界（猜测有3指针解），t4是熟悉的配方(第310周赛t4)，珂朵莉MM还是用了线段树，本质是查询并维护区间最值问题，推荐VP.
VP入口： 第222场周赛
更多的解题报告：珂朵莉MM的解题报告汇总
T1. 卡车上的最大单元数
题意稍有点绕，感觉说固定箱子数的价值最大化，可能更好理解些。
Java
class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
int n = boxTypes.length;
Arrays.sort(boxTypes, Comparator.comparing(x -> -x[1]));
int acc = 0;
for (int i = 0; i < n; i++) {
if (truckSize >= boxTypes[i][0]) {
truckSize -= boxTypes[i][0];
acc += boxTypes[i][0] * boxTypes[i][1];
} else {
acc += Math.min(boxTypes[i][0], truckSize) * boxTypes[i][1];
break;
}
}
return acc;
}
}T2. 大餐计数
经典的hash计数应用题，线性遍历过程，一边统计满足需求的pair对数，一边维护左侧hash的计数值。
时间复杂度为
Java
class Solution {
final int mod = 10_0000_0007;
// 最多 21 * n
public int countPairs(int[] deliciousness) {
Map<Integer, Integer> hash = new HashMap<>();
long ans = 0l;
for (int v: deliciousness) {
for (int i = 0; i <= 21; i++) {
if ((1 << i) >= v) {
ans += hash.getOrDefault((1 << i) - v, 0);
ans = ans % mod;
}
}
hash.put(v, hash.getOrDefault(v, 0) + 1);
}
return (int)ans;
}
}T3. 将数组分成三个子数组的方案数
因为涉及区间和，所以先处理一个前缀和。
然后整体的思路，是枚举第一个区间的右端点，找第二个区间的右端点的上下界。
上界就是，和最接近第三个区间的总和的点。
下界就是，大于等于第一个区间的和的点。
不过这里，需要注意区间为非空，全0的case，易错。
不过这边，珂朵莉MM总觉得存在三指针的解，^_^.
Java
class Solution {
// 闭区间[S, E]
int ceiling(long[] presum, int s, int e, long sk) {
int l = s, r = e;
while (l <= r) {
int m = l + (r - l) / 2;
if (presum[m + 1] - presum[s] >= sk) {
r = m - 1;
} else {
l = m + 1;
}
}
return l;
}
int floor(long[] presum, int s, int e, long sk) {
int l = s, r = e;
while (l <= r) {
int m = l + (r - l) / 2;
if (presum[m + 1] - presum[s] <= sk) {
l = m + 1;
} else {
r = m - 1;
}
}
return r;
}
// 前缀和 + 二分？
public int waysToSplit(int[] nums) {
int n = nums.length;
long[] presum = new long[n + 1];
for (int i = 0; i < n; i++) {
presum[i + 1] = presum[i] + nums[i];
}
int ans = 0;
for (int i = 0; i < n - 2; i++) {
long first = presum[i + 1];
int pos = ceiling(presum, i + 1, n - 1, first);
int mpos = floor(presum, i + 1, n - 1, (presum[n] - presum[i + 1]) / 2);
mpos = Math.min(n - 2, mpos);
if (pos < n - 1 && mpos >= pos) {
ans += (mpos - pos + 1);
ans = ans % 10_0000_0007;
}
}
return ans;
}
}T4. 得到子序列的最少操作次数
抛开算法本身，光就题意而言，有一个词，一定可以引起你的注意，那就是target数组的元素，各不相同. 其实这题的突破口也就在这里.
本质就是寻求以某个元素结尾，往前回溯，最长的子序列。
这两个问题应该等价。
不过这题，除了线段树，其他支持RMQ的数据结构应该也可以。
Java
class Solution {
static class Seg {
int l, r, m;
Seg left, right;
int v;
public static Seg create(int l, int r, int v) {
Seg s = new Seg();
s.l = l;
s.r = r;
s.m = l + (r - l) / 2;
s.v = v;
return s;
}
public static void update(Seg root, int p, int v) {
if (root.l == root.r) {
root.v = Math.max(root.v, v);
return;
}
if (root.left == null) root.left = Seg.create(root.l, root.m, 0);
if (root.right == null) root.right = Seg.create(root.m + 1, root.r, 0);
if (p <= root.m) {
Seg.update(root.left, p, v);
} else {
Seg.update(root.right, p, v);
}
root.v = Math.max(root.left.v, root.right.v);
}
public static int query(Seg root, int l, int r) {
if (root == null) return 0;
if (r < l) return 0;
if (root.l == root.r) return root.v;
if (l <= root.l && r >= root.r) {
return root.v;
}
int m = root.m;
if (l <= m && m < r) {
return Math.max(Seg.query(root.left, l, m), Seg.query(root.right, m + 1, r));
} else if (r <= m) {
return Seg.query(root.left, l, r);
} else {
return Seg.query(root.right, l, r);
}
}
}
public int minOperations(int[] target, int[] arr) {
int n = target.length;
Map<Integer, Integer> hash = new HashMap<>();
for (int i = 0; i < target.length; i++) {
hash.put(target[i], i);
}
Seg root = Seg.create(0, n - 1, 0);
int ans = n;
for (int i = 0; i < arr.length; i++) {
int v = arr[i];
if (!hash.containsKey(v)) {
int mv = Seg.query(root, 0, n - 1);
ans = Math.min(n - mv, ans);
} else {
int idx = hash.get(v);
int bl = Seg.query(root, 0, idx - 1) + 1;
Seg.update(root, idx, bl);
ans = Math.min(ans, n - bl);
}
}
return ans;
}
}写在最后
评论 (0)
