leetcode-C语言-3479.水果成篮 III

解析题目有以下特点：

1. 篮子中只能放置一种水果，可在找到对应篮子后将其置0表示不可再放置
2. 水果不能拆分放到两个篮子

解析题目有以下问题：

1. 如何在数组中找到大于目标数量的第一个值的索引 ：

• 暴力解法：直接遍历，找到值后将该值置为0
• 分块：查看题解有此解法，将数组划分为$\sqrt{n}$个区间，从左到右依次比较，时间复杂度为$O[n\ast \sqrt{n}]$ (n为遍历fruits,)
• 线段树：通过线段树记录区间的最大值，查询线段树。由于没有区间最大值没有顺序，最大时间复杂度为$O[n^2]$,但通过剪枝在实际运行可降低复杂度。

代码如下：

int Lchild(int root) {return root << 1;
}
int Rchild(int root) {return (root << 1) | 1;
}
// 建立线段树
void Build(int tree[], int baskets[], int root, int l, int r) {if(l == r) {tree[root] = baskets[l-1];return;}int mid = l + ((r - l) >> 1);Build(tree, baskets, Lchild(root), l, mid);Build(tree, baskets, Rchild(root), mid+1, r);tree[root] = tree[Lchild(root)] > tree[Rchild(root)] ? tree[Lchild(root)] : tree[Rchild(root)];return;
}
// 更新线段树
void Update(int tree[], int root, int l, int r, int pos, int value) {if(l == r) {tree[root] = value;return;}int mid = l + ((r - l) >> 1);if(pos <= mid) {Update(tree, Lchild(root), l, mid, pos, value);}else {Update(tree, Rchild(root), mid+1, r, pos, value);}tree[root] = tree[Lchild(root)] > tree[Rchild(root)] ? tree[Lchild(root)] : tree[Rchild(root)];return;
}
// 查询线段树
int Query(int tree[], int root, int l, int r, int fruitNum) {if(l == r) {return tree[root] >= fruitNum ? l-1 : -1;}// 剪枝if(tree[root] < fruitNum) return -1;int mid = l + ((r - l) >> 1);int tmp = Query(tree, Lchild(root), l, mid, fruitNum);if(tmp != -1) return tmp;tmp = Query(tree, Rchild(root), mid+1, r, fruitNum);return tmp;
}int numOfUnplacedFruits(int* fruits, int fruitsSize, int* baskets, int basketsSize) {// 设置线段树的长度为叶子节点这一层为满二叉树时的数量的二倍int n = log(basketsSize)/log(2);if(basketsSize > (1<<n)) n++;n = (1 << n);n = (n << 1);int tree[n+1];memset(tree, 0, sizeof(int)*(n+1));Build(tree, baskets, 1, 1, basketsSize);int res = 0;for(int i=0; i<fruitsSize; i++) {// 返回大于fruits[i]的篮子索引int idex = Query(tree, 1, 1, basketsSize, fruits[i]);if(idex != -1) Update(tree, 1, 1, basketsSize, idex+1, 0);else res++;}return res;
}