题目链接:poj 2828 Buy Tickets
题目大意:给定N,表示有个人,给定每个人站入的位置,以及这个人的权值,现在按队列的顺序输出每个人的权值。
解题思路:第K大元素,很巧妙,将人入队的顺序倒过来看,就是纯第K大问题,然后用树状数组还是线段树就都可以做了。
C++ 线段树
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200005;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)+1)
struct Node {
int l, r, s;
void set(int l, int r, int s) {
this->l = l;
this->r = r;
this->s = s;
}
}nd[maxn * 4];
int N, val[maxn], pos[maxn], rec[maxn];
void build (int u, int l, int r) {
nd[u].set(l, r, r - l + 1);
if (l == r)
return ;
int mid = (l + r) / 2;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
}
int query (int u, int x) {
nd[u].s--;
if (nd[u].l == nd[u].r)
return nd[u].l;
if (nd[lson(u)].s >= x)
return query(lson(u), x);
else
return query(rson(u), x - nd[lson(u)].s);
}
int main () {
while (scanf("%d", &N) == 1) {
build(1, 0, N - 1);
for (int i = 0; i < N; i++)
scanf("%d%d", &pos[i], &val[i]);
for (int i = N - 1; i >= 0; i--)
rec[query(1, pos[i] + 1)] = i;
printf("%d", val[rec[0]]);
for (int i = 1; i < N; i++)
printf(" %d", val[rec[i]]);
printf("\n");
}
return 0;
}
C++ 树状数组
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200005;
#define lowbit(x) ((x)&(-x))
int N, fenw[maxn], pos[maxn], val[maxn], rec[maxn];
void add (int x, int v) {
while (x <= N) {
fenw[x] += v;
x += lowbit(x);
}
}
int find (int x) {
int p = 0, s = 0;
for (int i = 20; i >= 0; i--) {
p += (1<<i);
if (p > N || s + fenw[p] >= x)
p -= (1<<i);
else
s += fenw[p];
}
return p + 1;
}
int main () {
while (scanf("%d", &N) == 1) {
memset(fenw, 0, sizeof(fenw));
for (int i = 1; i <= N; i++) {
add(i, 1);
scanf("%d%d", &pos[i], &val[i]);
}
for (int i = N; i; i--) {
int tmp = find(pos[i] + 1);
rec[tmp] = i;
add(tmp, -1);
}
for (int i = 1; i <= N; i++)
printf("%d%c", val[rec[i]], i == N ? '\n' : ' ');
}
return 0;
}
分享到:
相关推荐
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
NULL 博文链接:https://128kj.iteye.com/blog/1744222
poj2828解题报告,希望能帮到志同道合的算法爱好者
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1746750
NULL 博文链接:https://128kj.iteye.com/blog/1747400
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
线段树、树状数组算法入门 加 poj解题报告 pdf文档
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
NULL 博文链接:https://128kj.iteye.com/blog/1745671
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1739064
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
poj 2763 程序 线段树 LCA 2000MS AC
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ题解 个人写法 线段树每个人都不一样
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......