乐扣差个题没补
打没心态了，早上IEEE TSC rejected + 1
乐扣打着打着发现全球名字= 国服名次*10（一年没打过了）
做了仨（实际上是俩
将水果放入篮子 II3
给你两个长度为 n 的整数数组，fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的 数量，baskets[j] 表示第 j 个篮子的 容量。
你需要对 fruits 数组从左到右按照以下规则放置水果：
- 每种水果必须放入第一个 容量大于等于 该水果数量的 最左侧可用篮子 中。
- 每个篮子只能装 一种 水果。
- 如果一种水果 无法放入 任何篮子，它将保持 未放置。
返回所有可能分配完成后，剩余未放置的水果种类的数量。
示例 1
输入： fruits = [4,2,5], baskets = [3,5,4]
输出： 1
解释：
fruits[0] = 4放入baskets[1] = 5。fruits[1] = 2放入baskets[0] = 3。fruits[2] = 5无法放入baskets[2] = 4。
由于有一种水果未放置，我们返回 1。
示例 2
输入： fruits = [3,6,1], baskets = [6,4,7]
输出： 0
解释：
fruits[0] = 3放入baskets[0] = 6。fruits[1] = 6无法放入baskets[1] = 4（容量不足），但可以放入下一个可用的篮子baskets[2] = 7。fruits[2] = 1放入baskets[1] = 4。
由于所有水果都已成功放置，我们返回 0。
提示：
n == fruits.length == baskets.length1 <= n <= 1001 <= fruits[i], baskets[i] <= 1000
实际上就是从左到右招第一个大于fruits[i]的值，然后这个值就不能再用了。
朴素解法数据访问n =100可以直接for 套 for
高级解法可以把每个值找左边第一个大于他的值用数据结构维护成log的，则整体复杂度为$nlgn$
class segTree {
public:
struct node {
int l, r, lazy;
long long data;
};
vector<node> tree;
vector<long long> a;
segTree(int n) {
a.resize(n + 1);
tree.resize((n + 1) * 4);
}
void pushup(int x) {
tree[x].data = max(tree[x << 1].data, tree[x << 1 | 1].data);
}
void bulid(int x, int l, int r) {
if (l == r)
tree[x] = {l, r, 0, a[l]};
else {
tree[x] = {l, r, 0, 0};
int mid = (l + r) >> 1;
bulid(x << 1, l, mid);
bulid(x << 1 | 1, mid + 1, r);
pushup(x);
}
}
void pushdown(int x) {
if (tree[x].lazy) {
tree[x << 1].data += tree[x].lazy;
tree[x << 1 | 1].data += tree[x].lazy;
tree[x << 1].lazy += tree[x].lazy;
tree[x << 1 | 1].lazy += tree[x].lazy;
tree[x].lazy = 0;
}
}
void modify(int u, int p, long long v) {
if (tree[u].l == p && tree[u].r == p)
tree[u].data = v;
else {
int mid = (tree[u].l + tree[u].r) >> 1;
if (p <= mid)
modify(u << 1, p, v);
else
modify(u << 1 | 1, p, v);
pushup(u);
}
}
void update(int x, int l, int r, long long d) {
if (tree[x].l >= l && tree[x].r <= r) {
tree[x].data += d;
tree[x].lazy += d;
} else {
pushdown(x);
int mid = (tree[x].l + tree[x].r) >> 1;
if (l <= mid) update(x << 1, l, r, d);
if (r > mid) update(x << 1 | 1, l, r, d);
pushup(x);
}
}
long long query(int x, int l, int r) {
if (tree[x].l >= l && tree[x].r <= r) return tree[x].data;
pushdown(x);
int mid = (tree[x].l + tree[x].r) >> 1;
long long res = 0;
if (l <= mid) res = max(res, query(x << 1, l, r));
if (r > mid) res = max(res, query(x << 1 | 1, l, r));
return res;
}
int findLeftmost(int x, int l, int r, long long val) {
if (tree[x].data < val) return -1;
if (l == r) return l;
pushdown(x);
int mid = (l + r) >> 1;
if (tree[x << 1].data >= val) return findLeftmost(x << 1, l, mid, val);
return findLeftmost(x << 1 | 1, mid + 1, r, val);
}
};
class Solution {
public:
int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
int n = fruits.size();
segTree st(n);
for (int i = 0; i < n; i++) st.a[i + 1] = baskets[i];
st.bulid(1, 1, n);
int ans = 0;
for (int i = 0; i < n; i++) {
long long need = fruits[i];
int pos = st.findLeftmost(1, 1, n, need);
if (pos == -1)
ans++;
else
st.modify(1, pos, 0);
}
return ans;
}
};函数解释，segment tree维护最大值，最常规的操作
int findLeftmost(int x, int l, int r, long long val) {
if (tree[x].data < val) return -1;
if (l == r) return l;
pushdown(x);
int mid = (l + r) >> 1;
if (tree[x << 1].data >= val) return findLeftmost(x << 1, l, mid, val);
return findLeftmost(x << 1 | 1, mid + 1, r, val);
}找左边第一个大于val的数
如果当前节点的data比val小了，则说明当前节点及对应子树的值均小于$val$,不需要搜索
如果当前节点的左右指针相等代表找到了叶子节点，则返回当前坐标。
对于非叶子节点的搜索，优先搜索左子树，然后搜索右子树
最终返回结果为左边大于val的第一个元素的下标，-1为没有找到
元素用完后标记为最小值0，继续查找下一个，对未找到可行的值的情况下记录次数即为结果
选出和最大的 K 个元素
给你两个整数数组，nums1 和 nums2，长度均为 n，以及一个正整数 k 。
对从 0 到 n - 1 每个下标 i ，执行下述操作：
- 找出所有满足
nums1[j]小于nums1[i]的下标j。 - 从这些下标对应的
nums2[j]中选出 至多k个，并 最大化 这些值的总和作为结果。
返回一个长度为 n 的数组 answer ，其中 answer[i] 表示对应下标 i 的结果。
示例 1：
输入：nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2
输出：[80,30,0,80,50]
解释：
- 对于
i = 0：满足nums1[j] < nums1[0]的下标为[1, 2, 4]，选出其中值最大的两个，结果为50 + 30 = 80。 - 对于
i = 1：满足nums1[j] < nums1[1]的下标为[2]，只能选择这个值，结果为30。 - 对于
i = 2：不存在满足nums1[j] < nums1[2]的下标，结果为0。 - 对于
i = 3：满足nums1[j] < nums1[3]的下标为[0, 1, 2, 4]，选出其中值最大的两个，结果为50 + 30 = 80。 - 对于
i = 4：满足nums1[j] < nums1[4]的下标为[1, 2]，选出其中值最大的两个，结果为30 + 20 = 50。
示例 2：
输入：nums1 = [2,2,2,2], nums2 = [3,1,2,3], k = 1
输出：[0,0,0,0]
解释：由于 nums1 中的所有元素相等，不存在满足条件 nums1[j] < nums1[i]，所有位置的结果都是 0 。
提示：
n == nums1.length == nums2.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 1061 <= k <= n
离线操作，很明显可以按照nums1的顺序不断增加，同时维护小于当前nums1中的最大值的索引（最后一个加入的值）的nums2的值的数组
对前面的数值最大的$k$个用小顶堆维护，如果加入元素比最小的大，则去掉最小的加入最大的
更新当前堆的和，记录为当前结果
对于nums1中连续出现的相同值，采用双指针
先更新答案，后维护堆即可
class Solution {
public:
vector<long long> findMaxSum(vector<int>& nums1, vector<int>& nums2, int k) {
vector<array<int, 3>> n1;
for(int i = 0; i < nums1.size(); i++){
n1.push_back({nums1[i], nums2[i], i});
}
sort(n1.begin(), n1.end());
priority_queue<int> pq;
long long sum = 0;
vector<long long> ans(nums1.size());
for(int i = 0; i < nums1.size(); i++){
int r = i;
while(r < nums1.size() && n1[r][0] == n1[i][0]){
r ++;
}
for(int j = i; j < r; j++){
ans[n1[j][2]] = sum;
}
for(int j = i; j < r; j++){
int v = n1[j][1];
if(pq.size() < k){
sum += v;
pq.push(-v);
}else if(v > -pq.top()){
sum += pq.top() + v;
pq.pop();
pq.push(-v);
}
}
i = r - 1;
}
return ans;
}
};
Comments | NOTHING