Poj(2182)——Lost Cows(线段树)
发布日期:2021-09-19 06:09:08
浏览次数:17
分类:技术文章
本文共 2452 字,大约阅读时间需要 8 分钟。
Description
N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands. Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow. Given this data, tell FJ the exact ordering of the cows.
Input
* Line 1: A single integer, N * Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.
Output
* Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.
最近学了一下线段树,把基本题目都做了一下,但是一直都没有时间来总结一下,所以现在抽空总结了一下。
这道题的题意大致是:
有N头奶牛,编号为1~N,乱序排成一列,现在已知每头牛前面有多少头牛比它的编号小,求排队后从前往后数,每头牛的编号。
注意因为第一头牛前面肯定只有0头牛比它的编号小,那么题目这里没有给出,所以我们要自己加上去。
一开始没想到要怎么用线段树,看了一下题解后,然后懂了。
首先我们从后往前扫描,然后遇到数字a,就说明它是原先剩余序列中第a+1个数,找到该编号后删除,然后继续重复上述的操作。那么哪里用到了线段树呢?找的过程要用到线段树,看一个区间内未被删除的数字个数能否满足使当前要找的数成为第a+1个,能则递归左子树,否则递归右子树,那么叶子节点的值就是其初始编号。
#include#include #define maxn 10000int small[maxn],ans[maxn]; //ans是用来存储结果的; struct node{ int lc,rc,len;}s[4*maxn];void build(int root,int lc,int rc){ s[root].lc=lc; s[root].rc=rc; s[root].len=rc-lc+1; if(lc==rc) return ; build(2*root,lc,(lc+rc)/2); build(2*root+1,(lc+rc)/2+1,rc);}int query(int root,int k){ s[root].len--; if(s[root].lc==s[root].rc)return s[root].lc; else if(s[2*root].len>=k) return query(root*2,k); else return query(root*2+1,k-s[root*2].len);}int main(){ int n; scanf("%d",&n); for(int i=2;i<=n;i++) scanf("%d",&small[i]); small[1]=0; build(1,1,n); for(int i=n;i>=1;i--){ //这里的意思是:前面有几个比它小的,那么它就在原来的地方排第small+1位; ans[i]=query(1,small[i]+1); } for(int i=1;i<=n;i++) printf("%d\n",ans[i]);}
转载地址:https://blog.csdn.net/ACMer_hades/article/details/46272605 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月25日 16时08分01秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
jQuery日期选择器插件date-input
2019-04-27
PHP使用curl_multi_add_handle并行处理
2019-04-27
NP问题
2019-04-27
AT&T与Intel汇编语言的比较
2019-04-27
javascript解析json
2019-04-27
WinDbg安装与使用
2019-04-27
推荐阅读的多核编程技术书籍
2019-04-27
维基百科上的算法和数据结构链接很强大
2019-04-27
选择排序
2019-04-27
PHP session回收机制
2019-04-27
最新的全球编程语言,操作系统,web服务器等使用率分析报告
2019-04-27
用C语言写PHP扩展
2019-04-27
PHP Extension programming
2019-04-27
海量数据处理
2019-04-27
PHP防止注入攻击
2019-04-27
多路IO复用模型 select epoll 等
2019-04-27
Linux Epoll介绍和程序实例
2019-04-27
output_buffering详细介绍
2019-04-27
php缓冲 output_buffering和ob_start
2019-04-27
php error_reporting 详解
2019-04-27