基本思路就是,从后往前读取数字small[i]。在剩余编号集合里(一开始剩余编号集合为全集)查找第small[i]+1个编号,该编号就是对应位置牛的编号。

若直接用数组来做,则每次查找都需要遍历前n个数。而用线段树来做则可以降低为nlogn的复杂度。

事实上感觉可以直接用stl的set来做,直接模拟应该也能不超时得解。

本题主要用来熟悉线段树这个结构。

ac代码如下:

#include<iostream>
#include<cstdio>
#include<cstdio>
using namespace std;
const int maxn=;
int small[maxn],ans[maxn];
struct node{
int lc,rc,len;
};
node tree[maxn*];//这里一开始数组开小了出现了rte
void build(int x,int lc,int rc){
tree[x].lc=lc,tree[x].rc=rc;
tree[x].len=rc-lc+;
if(lc==rc)return ;
build(x*,lc,(lc+rc)/);
build(x*+,(lc+rc)/+,rc);
}
int query(int base,int k){
tree[base].len--;
if(tree[base].lc==tree[base].rc)return tree[base].lc;
if(k<=tree[base*].len){
return query(base*,k);
}
else{
return query(base*+,k-tree[base*].len);
}
}
int main(void){
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&small[i]);
}
small[]=;
build(,,n);
for(int i=n;i>=;i--){
ans[i]=query(,small[i]+);
}
for(int i=;i<=n;i++){
printf("%d\n",ans[i]);
}
return ;
}

最新文章

  1. oracle返回多个参数
  2. hibernate反向生成映射文件报错
  3. glsl计算sprite的亮度饱和度对比度
  4. 获取不到app.config里面的数据库连接字符串的解决方法
  5. Thinkphp 缓存微信jssdk相关认证参数
  6. CANoe 入门 Step by step系列(一)基础应用【转】
  7. a标签中调用js的几种方法
  8. [COGS 1065] 绿豆蛙的归宿
  9. IE9下table th不显示边框解决方法
  10. 80x86的内存寻址机制
  11. javase每天内容总结(32期)
  12. pngencoder图像转换jar
  13. MHL相关资源链接
  14. package &#39;yaml-cpp&#39; not found
  15. hdu3089 Josephus again|快速约瑟夫环
  16. Android Issue分析方法(用anr来说明)
  17. Qt 学习之路 2(44):QFileSystemModel
  18. HDU - 3072 Intelligence System
  19. mac的vim使用
  20. Xcode5 如何添加一个Github/Repository 并且Checkout

热门文章

  1. 转!!Linux 里的 2&gt;&amp;1 究竟是什么
  2. 【非root用户】安装【python,pip,package】
  3. CF #301 E:Infinite Inversions(逆序数,树状数组)
  4. js获取浏览器信息及版本(兼容IE)
  5. Saltstack之SSH简介
  6. nodejs获取参数的方法
  7. SIP UserAgent (B2BUA client)——pjsip
  8. Spark的集群管理器
  9. 转Hibernate 一对多关联的CRUD__@ManyToOne(cascade=(CascadeType.ALL))
  10. 利用crontab系统每天定时备份MySQL数据库及删除指定crontab定时任务