FZU 2136 取糖果

题目链接

题意：中文题

思路：线段树，先把所有糖果按价值排序，然后线段树结点表示糖果有无，如果当前找不到一个连续段满足长度，就继续加糖果，如果满足，答案就是最后加入的那个糖果，利用线段树的区间合并去找连续段长度

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100005;
struct Candy {
int val, id;
} c[N];
bool cmp(Candy a, Candy b) {
return a.val < b.val;
}
int t, n;
#define lson(x) ((x<<1)+1)
#define rson(x) ((x<<1)+2)
struct Node {
int l, r, lsum, rsum, sum;
int size() {return r - l + 1;}
} node[4 * N];
void build(int l, int r, int x = 0) {
node[x].l = l; node[x].r = r;
node[x].lsum = node[x].rsum = node[x].sum = 0;
if (l == r) return;
int mid = (l + r) / 2;
build(l, mid, lson(x));
build(mid + 1, r, rson(x));
}
void pushup(int x) {
node[x].lsum = node[lson(x)].lsum;
node[x].rsum = node[rson(x)].rsum;
node[x].sum = max(node[lson(x)].sum, node[rson(x)].sum);
if (node[lson(x)].lsum == node[lson(x)].size())
node[x].lsum += node[rson(x)].lsum;
if (node[rson(x)].rsum == node[rson(x)].size())
node[x].rsum += node[lson(x)].rsum;
node[x].sum = max(node[x].sum, node[lson(x)].rsum + node[rson(x)].lsum);
}
void add(int v, int x = 0) {
if (node[x].l == node[x].r) {
node[x].sum = node[x].lsum = node[x].rsum = 1;
return;
}
int mid = (node[x].l + node[x].r) / 2;
if (v <= mid) add(v, lson(x));
if (v > mid) add(v, rson(x));
pushup(x);
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
build(1, n);
for (int i = 1; i <= n; i++) {
scanf("%d", &c[i].val);
c[i].id = i;
}
sort(c + 1, c + n + 1, cmp);
int u = 1;
for (int i = 1; i <= n; i++) {
while (node[0].sum < i) add(c[u++].id);
printf("%dn", c[u - 1].val);
}
}
return 0;
}

最后

以上就是着急皮卡丘为你收集整理的FZU 2136 取糖果（线段树） FZU 2136 取糖果的全部内容，希望文章能够帮你解决FZU 2136 取糖果（线段树） FZU 2136 取糖果所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。