题目链接: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;
}
分享到:
相关推荐
java练习题
云南省移动应用大赛模板.zip
前台技术框架采用Bootstrap,一个高度灵活的HTML5响应式框架,为用户提供了流畅的前端交互体验。程序开发环境支持多样化,无论是myEclipse、Eclipse还是Idea都能轻松应对,结合mysql数据库,确保了数据的高效处理与存储。后台架构则选用SSM组合——SpringMVC、Spring和Mybatis,这一组合以其稳定性和高效性而备受青睐。 校园公益信息关联系统采用b/s架构,实现用户信息、活动类型、公益活动、活动报名、捐款、捐款统计、留言和新闻信息的全面管理。系统分为前台学生端和后台管理员端,满足不同用户群体的需求。 管理员端功能丰富,包括学院管理、活动类型管理、公益活动管理、活动报名管理、捐款信息管理、管理员账号管理、密码修改、捐款统计管理、留言管理和新闻信息管理等。管理员能够灵活添加、修改、删除和查询各类信息,确保信息的准确性和时效性。同时,捐款统计功能以直观的统计图形式展现,为管理员提供决策支持。 学生端则专注于学生的日常需求,包括添加捐款信息、留言、报名活动以及密码修改等。学生可以轻松完成捐款操作,发表留言,查看并报名公益活动,随时修改个人密码,确保账
JavaWeb程序设计SSM框架选课系统开发大作业有数据库文
行业分析报告
1、嵌入式物联网ESP32项目实战开发。例程经过精心编写,简单好用。 2、代码使用Visual Studio Code + ESP-IDF开发,C语言编程。例程在ESP32-S3上运行。若在其他型号上运行,请自行调整。 3、如果接入其他传感器,请查看发布的其他资料。 4、ESP32与模块的接线,在代码当中均有定义,请自行对照。 5、若硬件差异,请根据自身情况适当调整代码,程序仅供参考。 6、代码有注释说明,请耐心阅读。 7、技术v:349014857;
USB无线网卡驱动 USB\VID_1A86&PID_E397&REV_0738
TA-Lib(Technical Analysis Library, 即技术分析库)是Python金融量化的高级库,涵盖了150多种股票、期货交易软件中常用的技术分析指标,如MACD、RSI、KDJ、动量指标、布林带等。但很多人安装指标计算ta-lib库就总报错,就可以在这里找到包下载后安装。 文件举例:TA_Lib‑0.4.24‑cp37‑cp37m‑win_amd64.whl 命名解释:包名-版本号-cp37代表适用于python3.7版本-win代表windows平台-amd64表示64位版本(与python版本要一致) 假定文件下载到d盘根目录,使用如下命令进行安装: pip install d:\TA_Lib‑0.4.24‑cp37‑cp37m‑win_amd64.whl
电子通信设计资料电动智能小车设计论文资料提取方式是百度网盘分享地址
调节篮球比赛定时器,毕业设计实验报告,multisim仿真,AD09原理图及PCB图
编程题实训-串
汉诺塔c语言递归
行业分析报告
电子通信设计资料单片机串行通信发射机论文资料提取方式是百度网盘分享地址
完整代码!扫雷游戏,vs2010使用vs2010开发小游戏,这是一个扫雷的游戏,适应于大作业和毕业论文.zip
基于JAVA毕业设计-JAVA图书馆书库管理系统设计(论文+源代码).rar 毕业设计(论文)是考核应考者综合运用所学基础理论和专业技能,独立分析和解决实际问题的能力。计算机应用专业培养从事计算机软件和硬件设计,开发和应用的高层次人才,检测考生是否阅读了必要的中外文献,能否运用科技合理的定性和定量分析,来设计和实现设计系统。 图书馆书库管理系统主要是完成图书管理员对图书的管理(增加新书,删除旧书,并修改等的图书编辑);图书管理员对读者借还书的统计(图书的在库数目和还日期的统计)和管理;读者和管理员对图书信息和读者信息的查询;当查到所需信息时,打印出相应的信息报表等工作。 在图书馆书库管理系统的设计与实现过程中,我深深体会到此次毕业设计的重要性------它是我走上工作岗位前的一次重要的练习,更深刻体会到理论联系实践的重要性和必要性。同时,我也感受到JAVA 和SQL SERVER 2000 的功能之强大,事件处理的灵活性和高效性。但我掌握和应用的还不是很熟练,应多加实践和练习,在以后的工作中,我将不断的学习和充实自己,力争成为一个高水平的程序员。
行业分析报告
mybatis-plus-extension.jar 各个版本,免费下载。 mybatis-plus 的扩展插件。,各个版本,免费下载。 mybatis 增强工具包的扩展插件,各个版本,免费下载。 下载不了,可关注我,评论区联系我。
halcon缺陷检测
1000+套最新计算机专业毕业设计源码+论文+PPT.txt.zip